class Solution {
    
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    
    // 고유한 정수 집합의 서브셋
    // Backtracking: Decision Tree
    // T: O(n*2^n), S: O(n)
    public List<List<Integer>> subsets(int[] nums) {
       backtrack(nums, 0);
        
       return list;
    }

    private void backtrack(int[] nums, int start) {
        // 모든 가능한 서브셋이므로 항상 추가(리스트에 복사하기 위해서 O(n) 이 필요)
        list.add(new ArrayList<>(temp));
        
        for (int i = start; i < nums.length; i++) { 
            temp.add(nums[i]);
            // 중복 포함하지 않으므로 시작 인덱스를 변경해야 한다.
            backtrack(nums, i + 1);
            temp.remove(temp.size() - 1);
        }
    } 
}

class Solution {
    
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    
    // T: O(n2^n)
    public List<List<Integer>> subsets(int[] nums) {
        solve(nums, 0);
        return list;
    }
    
    public void solve(int nums[], int i){
        // 마지막 항목이면 결과 집합에 추가하고 종료
        if (i == nums.length) {
            list.add(new ArrayList<>(temp));
            return;
        }
        
        //선택된 경우
        temp.add(nums[i]);
        solve(nums, i + 1);
        
        //선택안된 경우(리스트에서 마지막 항목 삭제)
        temp.remove(temp.size() - 1);
        solve(nums, i + 1);
    }
}