[LeetCode] Permutations

문제

https://leetcode.com/problems/permutations/

알고리즘

순열, 백트래킹

풀이

기존에 Array로 풀때랑 다르게 List로 푸니까 헷갈렸던 거 같다.

백트래킹

방문한 배열값도 지우고 실제 List의 값도 지워줘야 기존 값을 지우고 다른값을 채울 수 있다.

코드

class Solution {
    static int[] check;
    List<List<Integer>> answer = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {

        check = new int[nums.length];
        ArrayList<Integer> list = new ArrayList<>();
        dfs(0, nums, list);

        return answer;
    }

    public void dfs(int L, int[] nums, List<Integer> list) {
        if (L == nums.length) {
            answer.add(new ArrayList<>(list));
        } else {

            for (int i = 0; i < nums.length; i++) {
                if (check[i] == 0) {
                    list.add(nums[i]);
                    check[i] = 1;
                    dfs(L + 1, nums, list);
                    check[i] = 0;
                    list.remove(list.size() - 1);
                }
            }
        }

    }
}