[LeetCode- Ch9. 백트래킹] 3. 부분집합

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

Subsets - LeetCode

 

 

1. 2^n개의 부분집합을 모두 나열

2. 배열의 길이만큼 돌면서 DFS 수행

3. 배열의 길이보다 크면 리턴하고, 나머지는 해당 배열값을 current에 넣고, list에 존재하지 않으면 삽입

4. 모두 돌기위해서, 다음값을 더한 current와 다음값을 제거한 current로 나눠 DFS 수행

class Solution {
    //2^n개의 부분집합 : 순서가 존재하지 않는다.
    static int cnt=0;
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result= new ArrayList<>();
        List<Integer> list = new ArrayList<>();        
        result.add(list);
        for(int i=0;i<nums.length;i++){
            list = new ArrayList<>();        
            System.out.println(i+"번째");
            DFS(i, nums, result, list);
        }
        
        
        return result;
    }
    private void DFS(int L, int[] nums, List<List<Integer>> lists, List<Integer> cur){
        if(L>=nums.length) return;
        cur.add(nums[L]);

        List<Integer> list = new ArrayList<>(cur);
        if(!lists.contains(list)) lists.add(list);
        
        if(cur.size()<=nums.length) {
            System.out.println(L+" "+nums[L]);
            DFS(L+1, nums,lists,cur);         
            cur.remove(cur.size()-1);
            DFS(L+1, nums,lists,cur);
        }
    }
}

 

+) 세련된 풀이

class Solution {
    //2^n개의 부분집합 : 순서가 존재하지 않는다.
    static int cnt=0;
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result= new ArrayList<>();
        List<Integer> list = new ArrayList<>();  
        
        if(nums==null || nums.length==0) return result;
        
        DFS(0, nums, result, list);
    
        
        
        return result;
    }
    private void DFS(int L, int[] nums, List<List<Integer>> lists, List<Integer> cur){
        //1. 원하는 조건을 충족한 값들을 담는다. 
        //-> cur가 전달받은 파라미터이기 떄문에 새로운 그릇에 담아서 추가
        List<Integer> list = new ArrayList<>(cur);
        lists.add(list);
        
        //2. for 저장, 탈출
        //(1) 현재 값 저장
        //(2) 다음 DFS 호출(현재 인덱스에서 +1한 값 호출)
        //(3) 호출한 값 제거(마지막 값 제거)
        for(int i=L; i<nums.length;i++){
            cur.add(nums[i]);
            DFS(i+1, nums,lists, cur);
            cur.remove(cur.size()-1);
        }
    }
}