Leetcode Subsets in Java

문제

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

예

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

접근

순열 알고리즘을 공부한적이 있는데 유튜브에 잘 설명한 동영상이 있어서 먼저 순열에 대해 배웠다. 기본적으로 순열은 백트래킹을 통해 접근한다. 영상에서 설명한 코드는 아래와 같다.

public class Main {
   public static void main(String[] args) {
      // test case
       int[] arr = {1,2,3};
       int[] arr2 = {1,2,3,4};

       System.out.println(solution(arr));
   }

   public static List<List<Integer>> solution(int[] arr) {
       List<List<Integer>> answer = new ArrayList<>();
       List<Integer> temp = new ArrayList<>();

       backtrack(arr, temp, answer);

       return answer;
   }

   private static void backtrack(int[] arr, List<Integer> temp, List<List<Integer>> answer){
       // base case
       if(temp.size() == arr.length){
           answer.add(new ArrayList<>(temp));
           System.out.println("temp is full now adding to answer " + temp);
           return;
       }
       // recursion
       for(int i=0; i<arr.length; i++){
           if(temp.contains(arr[i])) continue;
           temp.add(arr[i]);
           System.out.println(arr[i] + " has added so temp will be " + temp);
           backtrack(arr, temp, answer);
           System.out.print(arr[temp.size()-1] + " has been deleted so temp will be ");
           temp.remove(temp.size()-1);
           System.out.println(temp);
       }
   }
}

바로 이해가 안가서 출력문으로 직접 확인하며 이해했는데 혹시 다른 사람이나 미래에 나에게 도움이 될까 출력문도 그냥 적어놓았다.

기본적으로 위 알고리즘을 통해 해결을 한다.

먼저 사이즈를 정하고 맞는 적합한 사이즈에 맞는 배열을 temp로 뽑아서 넣는다. 위 코드도 이번 문제의 코드도 그렇고 전부

answer.add(new ArrayList<>(temp));

temp 배열을 answer에 추가할 때 배열을 복사해주어야 하는점을 주의해야 한다. 왜냐하면 permutation 메소드의 for문에서 계속해서 temp를 통해 계산을 하고 있기 때문이다.

정답 코드는 아래와 같다.

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        backtrack(nums, temp, answer, 0);

        return answer;
    }
    
    private void backtrack(int[] nums, List<Integer> temp, List<List<Integer>> answer, int size){
        //base case
        if(size > nums.length) return;
        answer.add(new ArrayList<>(temp));

        //recursion
        for(int i=size; i<nums.length; i++){
            temp.add(nums[i]);
            backtrack(nums, temp, answer, i+1);
            temp.remove(temp.size()-1);
        }
    }
}

이 코드의 이어지는 콜스택에 대해 하나하나 설명하자면

1. [] -> added to answer
2. temp.add(nums[0])이 실행되어 temp에 [1]이 들어가고 다음 backtrack(2번째) 재귀를 통해 [1]이 바로 answer`에 푸시된다.
3. 두 번째 backtrack에서 size가 1이 되므로 1번째 인덱스인 2가 temp에 푸시되고 세 번째 backtrack에서 `[1,2]가 푸시된다.
4. 똑같이 [1,2,3]까지 answer 배열에 푸시된다.

여기부터 헷갈린다.

5. 베이스케이스에 걸려 네 번째 backtrack은 실행되지 않고
6. 세 번째, 두 번째 backtrack의 clean-up 즉 temp.remove(temp.size()-1이 실행되어 temp가 [1]이 되고 두 번째 backtrack의 다음 nums[i] 즉 3이 temp에 푸시된다.
7. answer에 [1,3]이 푸시 되고 clean-up을 통해 제거 된다음 가장 첫 번째 backtrack의 두 번째 nums[i] 즉 2가 다시 temp에 푸시되고 계속 이 과정이 반복된다.

결론

내 의식의 흐름대로 콜 스택의 진행을 썼지만 바로 까먹을 것 같다. 백트래킹으로 순열을 구현하는 글들이 코드가 굉장히 직관적이지 못해서 어렵다고 하고 심지어는 외우는게 좋다고 하는 글도 있다. 지금 당장 내가 쓴 글을 다시 봐도 이해가 잘 가지 않는다. 백트래킹 문제를 여러번 풀어서 익숙해지는 편이 좋을 것 같다.