.leetcode(46. Permutations)

문제

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

문제 풀기 전

1. 딱보니 result는 전역변수로 해서 recursion이 끝날때마다 add하는 형식으로 해야겠다.
2. 메소드를 하나 더 두고 index를 하나씩 추가해서 끝을 파악핟록 짜야겠다.
3. 채워져가는 배열이 하나 더 있어야겠다.

직접 푼 풀이

소요시간: 14분 (11:56 ~ 12:10)

class Solution {
    private List<List<Integer>> result;

    public List<List<Integer>> permute(int[] nums) {
        result = new ArrayList<>();

        doPermute(nums, 0, new int[nums.length]);

        return result;
    }

    private void doPermute(int[] nums, int index, int[] made) {
        if (index == nums.length) {
            List<Integer> one = new ArrayList<>();
            for(int i=0; i<nums.length; i++) {
                one.add(made[i]);
            }
            result.add(one);
            return;
        }

        for (int i=0; i<nums.length; i++) {
            if (nums[i]== -11) continue;
            made[index] = nums[i];
            nums[i] = -11;
            doPermute(nums, index+1, made);
            nums[i] = made[index];
        }
    }
}

느낀점

1. recursion인데 input데이터를 하나씩 지워나가느건 저런식으로 풀면 되는구나 했다. 그리고 제한값을 이용해 -11이라는 숫자는 없으므로 체크할 명목으로 쓰였다.
2. 조건이 맞는것만 recursion하니 이것도 backtracking이라고 할 수 있는거 같다.

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)