[알고리즘] Leetcode_78_Subsets

Problem

Solve

• 배열에서 가질 수 있는 모든 부분 집합 ➡️ 2^n 의 부분 집합의 개수를 가진다.
• 중복 허용 x ➡️ 중복 체크 위해 배열 visited 를 사용했으나 어차피 backtracking 재귀를 통해 넘겨주는 인덱스 파라미터는 현재 원소의 다음 원소부터 순회하면 되기 때문에 visited 배열을 굳이 사용하지 않아도 index+1 만을 사용하면 됨!
  ( 난, 둘 다 사용하고 있었기 때문에 테스트는 통과되었고, 시간은 조금 단축시킬 수는 있다.)

class Solution {
     public static void backtracking(int[] nums, boolean[] visited, List<List<Integer>> result, List<Integer> list, int index){
      // System.out.println("backtracking(nums, visited, result : "+result + " ,  list : "+ list + " , index : "+index+ " )");
        
         result.add(new ArrayList<>(list));
         
        //if(index >= nums.length) return; ➡️ 어차피 for문은 nums.length-1 까지 돌기 때문에 굳이 필요없음
		
        for(int i = index ; i < nums.length ; i++){
        	//중복 허용 x
            
            //내가 사용한 방법 : visited 배열로 중복 여부 확인
            if(!visited[i]){
           
                visited[i] = true;
                list.add(nums[i]);
                backtracking(nums, visited, result, list, i+1);
                list.remove(list.size()-1);
                visited[i] = false;
             
            }
            
            //이렇게만 해도 됨!
            list.add(nums[i]);
            backtracking(nums, result, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
    public static List<List<Integer>> subsets(int[] nums) {
        
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];

        backtracking(nums, visited, result, list, 0);


        return result;
    }
}