Subsets

https://leetcode.com/problems/subsets/description/

Subsets - LeetCode

 

주어진 배열의 모든 subset을 List로 리턴하는 문제이다.
각 요소를 순회하기 위하여 dfs로 백트래킹을 하여 가능하며, 중복 요소를 제거하기 위하여
현재 인덱스 이후 기준으로 dfs 탐색 하였다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> subsets(int[] nums) {  
        List<List<Integer>> answer = new ArrayList<>();  
        List<Integer> cur = new ArrayList<>();  
        boolean[] visited = new boolean[nums.length];  
        dfs(answer, cur, -1, visited, nums);  
  
        return answer;  
    }  
  
    private void dfs(List<List<Integer>> answer, List<Integer> cur, int curidx, boolean[] visited, int[] nums){  
        // Array 의 값을 복사하여 넣어준다.  
        List<Integer> subset = new ArrayList<>(cur);  
        answer.add(subset);  
  
        for(int i = curidx + 1; i < visited.length; i++){  
            if(!visited[i]){  
                cur.add(nums[i]);  
                int curSize = cur.size();  
                visited[i] = true;  
                dfs(answer, cur, i, visited, nums);  
                // 값을 다시 초기화하여 백트래킹 한다.  
                visited[i] = false;  
                cur.remove(curSize - 1);  
            }  
        }  
    }  
}

 

서브 셋을 추가할 땐 해당 배열을 복사해서 추가해주었다.

List의 참조 값을 바라보므로 해당 시점의 배열 요소로 복사해서 넣어주어야 한다.