(백트래킹) 78. Subsets

링크

배열에 있는 수를 넣었다 뺏다 해서 만들 수 있는 모든 배열을 순서에 상관 없이 반환하시오.

예시 ) [1] -> [],[1] 두개의 배열을 담은 리스트를 반환.

내가 생각한 접근 방법. 매우 비효율적
각 배열의 요소가 있는 경우와 없는 경우 이 두가지의 경우로 계속 반복됩니다.
그러면 0번째 인덱스부터 마지막 인덱스까지
숫자가 있는 배열 addedList, 숫자가 없는 배열 nonAddedList를 만들어 계속 Set에 더해주면(중복을 허락하지 않기 때문에)
답이 되지 않을까 싶어서 짰습니다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

class Solution {
    List<List<Integer>> answer;
    HashSet<List<Integer>> hs = new HashSet<>();

    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> list = new ArrayList<>();

        backtracking(list,0, nums);

        answer = new ArrayList<>(hs);

        return answer;
    }

    public void backtracking(List<Integer> list, int index, int[] nums) {
        //index가 배열의 크기보다 커지면 함수를 종료합니다.
        if (index > nums.length - 1) {
            return;
        }
        //숫자가 들어가는 경우의 리스트
        List<Integer> addedList = new ArrayList<>(list);
        //숫자가 안들어가는 경우의 리스트
        List<Integer> nonAddedList = new ArrayList<>(list);
        //숫자가 들어가는 리스트이므로 인덱스별 숫자를 넣어줌.
        addedList.add(nums[index]);

        //숫자가 들어간 경우의 수를 기준으로
        //다음 인덱스부터 다시 같은 메서드를 시작함.
        hs.add(addedList);
        //숫자가 들어가지 않은 경우의 수를 해쉬셋에 넣어줌.
        hs.add(nonAddedList);
        //인덱스는 증가해서 다음 수를 노리게함.
        index++;
        //숫자가 들어간 경우의 수를 기준으로
        //다음 인덱스부터 다시 같은 메서드를 시작함.
        backtracking(addedList, index, nums);
        //숫자가 안 들어간 경우의 수를 기준으로
        //다음 인덱스부터 다시 같은 메서드를 시작함.
        backtracking(nonAddedList, index, nums);
    }
}

코드의 문제점

쓸 데 없이 객체를 너무 많이 생성함.
예를 들어 {1,2,3}이 있으면 {1},{},{1,2},{1} 이런 식으로 중복 되는 경우의 수가 너무 많음.

백트래킹을 사용한 리트코드 최다 추천답안

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

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

솔직히 말해서 잘 모르겠음. 여러 번 더 봐야할 거 같고 백트래킹에 대한 개념이 아직 덜 잡혀서 그런 거 같다.
백트래킹이랑 재귀함수 개념이 좀 약한 거 같다. 한 번 찾아 보고 개념 문제도 많이 풀어봐야겠음.