[LeetCode#46] Permutation

❒ Description

---

제목	Permutation
링크	https://leetcode.com/problems/permutations/description/
자료구조	비선형 (그래프)
시간복잡도	O(n!)

Permutation(순열)이란, 모든 가능한 경우를 그래프 형태로 나열한 결과라고 할 수 있다.

이 문제는 BackTraking을 통해서 해결하는 문제인데, 모든 가능한 순열을 생성하기 때문에

nums의 크기가 커질수록 시간이 급격히 증가한다.

 

❒ Solution

---

1. Solution1

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> elements = Arrays.stream(nums).boxed().toList();
        dfs(results, new ArrayList<>(), elements);
        return results;
    }

    private void dfs(List<List<Integer>> results, List<Integer> prevElement, List<Integer> elements) {
        if (elements.isEmpty()) {
            results.add(prevElement.stream().toList());
        }

        for (Integer e : elements) {
            List<Integer> nextElements = new ArrayList<>(elements);
            nextElements.remove(e);

            prevElement.add(e);
            dfs(results, prevElement, nextElements);
            prevElement.remove(e);
        }
    }
}

 

 

2. Solution2

public class V2 {
    
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
        visited = new boolean[nums.length];
        backtrack(nums);
        return res;
    }

    private void backtrack(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            path.add(nums[i]);
            visited[i] = true;
            backtrack(nums);
            visited[i] = false;
            path.removeLast();
        }
    }
}

처음에 방문여부를 생각했었는데 구현은 못했었다.

Solution2가 코드를 이해하는데 더 쉬운 것 같다.