Permutations

LeetCode 46. Permutations

원문

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

풀이

백트래킹.

1. 지금까지 추가한 숫자 집합의 크기가 nums의 크기와 같다면 결과 배열에 집합을 추가한다.
2. 그렇지 않다면 nums를 순회한다. (인덱스는 i로 표기한다.)
   1. i가 방문처리 되어 있다면 넘어간다.
   2. 그렇지 않다면 i를 방문처리 한다.
   3. 숫자 집합에 nums[i]를 추가한다.
   4. 함수 재귀호출
   5. i의 방문처리를 취소한다.
   6. 숫자 집합에서 nums[i]를 제거한다.

코드

Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def permutation():
            if len(route) == len(nums):
                result.append(list(route))
                return

            for i in range(len(nums)):
                if not visited[i]:
                    visited[i] = True
                    route.append(nums[i])
                    permutation()
                    visited[i] = False
                    route.pop()


        visited = [False for i in range(len(nums))]
        result = list()
        route = list()
        permutation()

        return result

Java

class Solution {
    List<List<Integer>> result = new ArrayList<>();

    private void backtrack(List<Integer> numbers, int[] nums, Set<Integer> used) {
        if (numbers.size() == nums.length) {
            result.add(new ArrayList<>(numbers));
            return;
        }
        for (int num: nums) {
            if (used.contains(num)) {
                continue;
            }
            numbers.add(num);
            used.add(num);
            backtrack(numbers, nums, used);
            used.remove(num);
            numbers.remove(numbers.size() - 1);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        backtrack(new ArrayList<>(), nums, new HashSet<Integer>());
        return result;
    }
}