Problem

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.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Solution

核心思路

用回溯法来解决，寻找所有可能性的问题

回溯的核心意思就是：

1. 递归：把这个问题拆成多个步骤
   1. 终止条件
2. 每个步骤，我们要做不同的选择，得到不同的结果
3. 把这些结果都汇总在一起，就得到了所有的可能性

具体实现

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Set<Integer> subSet = new HashSet<>();
        helper(result, subSet, nums, 0);
        return result;
    }
    private void helper(List<List<Integer>> result, Set<Integer> subSet, int[] nums, int index){
        if(index == nums.length) {
            result.add(new ArrayList<>(subSet));
        } else {
            // 第一种选择，当前元素不加入子集
            helper(result, subSet, nums, index+1);
            // 第一种选择，当前元素加入子集
            subSet.add(nums[index]);
            helper(result, subSet, nums, index+1);
            subSet.remove(nums[index]);
        }
    }
}