[LeetCode] - 46. Permutations

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Permutations " 문제입니다.

--> https://leetcode.com/problems/permutations/description/

 

문제 : 

Given an array nums of distinct integers, return all the possible permutations.

You can return the answer in any order.

---

Example 1 :

Input : nums = [1,2,3]

Output : [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

Example 2 :

Input : nums = [0,1]

Output : [[0,1],[1,0]]

 

Example 3 :

Input : nums = [1]

Output : [[1]]

 

Constraints : 

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

---

이 문제는 주어진 정수 배열 nums의 모든 가능한 순열을 반환해야 합니다. 순열은 아무 순서로 반환해도 괜찮습니다.

class Solution {
    public List<List<Integer>> permute(int[] nums) {
       List<List<Integer>> perms = new ArrayList<>();
       List<Integer> res = new ArrayList<>();
       backtrack(perms, res, nums);
       return perms;
    }

    private void backtrack(List<List<Integer>> perms, List<Integer> res, int[] nums) {
        if (nums.length == res.size()) {
            perms.add(new ArrayList<>(res));
            return;
        }

        for (int num : nums) {
            if (!res.contains(num)) {
                res.add(num);
                backtrack(perms, res, nums);
                res.remove(res.size() - 1);
            }
        }
    }

   
}

 

이 코드는 주어진 배열 nums의 모든 가능한 순열을 구하는 방법을 구현합니다. 순열을 생성하기 위해 백트래킹(Backtracking) 기법을 사용합니다. 각 단계에서 가능한 모든 선택지를 시도하고, 선택지를 되돌려가며 모든 경우의 수를 탐색합니다.

주요 함수 설명

1. permute 함수
   • nums 배열을 입력으로 받아 모든 순열을 계산합니다.
   • perms 리스트를 초기화하여 최종 결과를 저장할 리스트로 사용합니다.
   • res 리스트를 초기화하여 현재 생성 중인 순열을 저장합니다.
   • backtrack 함수를 호출하여 순열 생성 과정을 시작합니다.
2. backtrack 함수
   • 재귀적으로 호출되어 순열을 생성합니다.
   • nums.length와 res.size()가 같으면 현재 생성된 순열이 완전한 하나의 순열이므로 이를 perms 리스트에 추가합니다.
   • nums 배열을 순회하며 아직 res 리스트에 포함되지 않은 숫자를 선택합니다.
   • 선택된 숫자를 res 리스트에 추가하고, 다시 backtrack 함수를 호출하여 다음 숫자를 선택합니다.
   • 재귀 호출이 완료되면, res 리스트에서 마지막으로 추가된 숫자를 제거하여 다음 선택지를 시도합니다.

시간 복잡도 :

• 순열을 생성하는 데 필요한 시간 복잡도는 O(n!)입니다. 여기서 n은 nums 배열의 길이입니다. 이는 n개의 요소로 가능한 모든 순열의 수가 n! 이기 때문입니다.
• 각 순열마다 요소를 추가하고 제거하는 데 O(n)의 시간이 걸립니다. 따라서 최종 시간 복잡도는 O(n * n!) 입니다.

공간 복잡도 :

• 공간 복잡도는 O(n)입니다. 여기서 n은 nums 배열의 길이입니다. 이는 백트래킹 호출 스택과 res 리스트에 의해 결정됩니다.
• 추가적으로, 모든 순열을 저장하는 데 O(n * n!)의 공간이 필요합니다. 이는 최종 결과 리스트의 크기와 관련이 있습니다.

---

솔루션들을 서핑하다가 되게 섬세하고 여러 접근 방식으로 써주신 분이 있어서 그분의 링크를 달아드리겠습니다. 꼭 한 번 보십시오!!

https://leetcode.com/problems/permutations/solutions/18239/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning

---

코드 Runtime 결과