Leetcode 78) Subsets

29 Jul 2021 in Algorithms

내 답안

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> cur = new ArrayList<>();
        helper(nums,0,cur);

        return res;
    }

    public void helper(int[] nums,int start, List<Integer> cur){
        res.add(cur);
        for(int i=start;i<nums.length;i++){
            List<Integer> tmp = new ArrayList<Integer>(cur);
            tmp.add(nums[i]);
            helper(nums,i+1,tmp);
        }

    }

}

다른 답안

class Solution {
    /**
    We need to implement backtrack
    Approach to the solution is a tree
    */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, result, new ArrayList<Integer>());
        return result;
    }

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