[LeetCode] 78. Subsets

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

---

Solution

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), nums, 0);
        return list;
    }
    private void backtrack(List<List<Integer>> list , List<Integer> tmpList, int[] nums, int start) {
        list.add(new ArrayList<>(tmpList));
        for (int i = start; i < nums.length; i++) {
            tmpList.add(nums[i]);
            backtrack(list, tmpList, nums, i + 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

Explanation

• 함수의 반환값은 아래와 같이 큰 리스트 속에 작은 리스트를 여러개 포함하고 있는 구조이다. 이는 작은 리스트 하나를 만들기 위한 반복과 만들어진 작은 리스트를 큰 리스트에 삽입하기 위한 반복이 필요하다는 의미가 된다.

  Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
  

• 문제의 함수는 리스트를 반환하도록 하고 있으므로, 일단 반환을 위한 큰 리스트인 list를 선언한다.

  List<List<Integer>> list = new ArrayList<>();
  

• 큰 리스트에 작은 리스트를 삽입하는 반복을 본 문제에서는 재귀함수를 선택하여 해결하도록 한다.
• 함수의 선언부에는 재귀 함수에 필요한 인수인 list, tmpList, nums를 선언하고, 함수의 구현부에서 tmpList를 list에 삽입하고, 재귀 함수를 호출하여 반복하도록 한다.

  private void backtrack(List<List<Integer>> list , List<Integer> tmpList, int[] nums) {
    list.add(new ArrayList<>(tmpList));
    backtrack(list, tmpList, nums);
  }
  

• 작은 리스트를 만들기 위해 재귀함수의 구현부에 for반복문을 작성한다. 작은 리스트에 값이 추가될 때 마다 큰 리스트에 추가되는 작업이 필요하므로, for반복문 안에서 재귀 함수를 호출하도록 한다.

  private void backtrack(List<List<Integer>> list , List<Integer> tmpList, int[] nums) {
    list.add(new ArrayList<>(tmpList));
    for (int i = 0; i < nums.length; i++) {
        tmpList.add(nums[i]);
        backtrack(list, tmpList, nums);
    }
  }
  

• 위와 같이 재귀 함수를 작성하여 호출하게 되면 동일한 tmpList를 list에 넣게 되므로, for반복문의 선언부에 변화를 줘서 같은 원소가 tmpList에 들어갈 수 없도록 만든다.
• 재귀 함수의 선언부에 for반복문의 시작 지점을 나타내는 변수 start를 추가하고, 재귀 함수를 호출할 때 시작 지점이 달라지도록, 1을 더해서 호출한다.
• 재귀 함수의 호출이 종료되어 재귀 함수를 호출한 곳으로 돌아 왔을 때, tmpList가 가득 차 있으면 안 되기 때문에, 재귀 함수의 호출이 종료되었을 때 tmpList의 마지막 요소를 삭제하도록 한다.

  private void backtrack(List<List<Integer>> list , List<Integer> tmpList, int[] nums, int start) {
    list.add(new ArrayList<>(tmpList));
    for (int i = start; i < nums.length; i++) {
        tmpList.add(nums[i]);
        backtrack(list, tmpList, nums, i + 1);
        tmpList.remove(tmpList.size() - 1);
    }
  }