기억하고싶은것들

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

중복되는 값이 없는 integer 배열이 주어진다.

가능한 모든 하위 집합을 반환하라.

해답에는 중복된 하위 집합을 포함하면 안 된다.

해답은 어떠한 순서도 상관없다.

가능한 모든 하위 집합을 반환하는 문제이다. 

Backtracking을 통해서 가능한 모든 조합을 탐색하고 조건이 만족하지 않는 경우는 패스해 보도록 하자.

여기서 조건이 만족하지 않는 경우는 이미 그전에 탐색에서 하위 집합에 포함된 원소이다.

    public void backtracking(List<List<Integer>> rst, ArrayList<Integer> list, int[] nums, int idx) {

        rst.add(new ArrayList<>(list));

        for (int i = idx; i < nums.length; i++) { // startIndex를 통해 이미 추가한 원소 필터링 
            list.add(nums[i]);
            backtracking(rst, list, nums, i + 1);
            list.remove(list.size() - 1);
        }
    }

그럼 다음으로 해당 메서드를 호출해주는 코드를 살펴보도록 하자.

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

        backtracking(rst, new ArrayList<Integer>(), nums, 0);
        return rst;
    }

출처 : https://leetcode.com/problems/subsets/