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]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

All the numbers of nums are unique.

---

给 元素不重复 无序 数组，求所有的子数组，组合问题

package leetcode.problems.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subsets {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);

        backtrack(result, path, nums, 0);
        return result;
    }

    /**
     * 回溯法 求不重复元素数组的全组合 子集
     * @param result 全部子集列表
     * @param path 尝试选择元素的可能性树的从根节点开始到当前节点的路径
     * @param nums 不重复元素数组
     * @param start 当前准备开始尝试start index后的全部数组
     */
    private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
        // 因为是求全部子数组，所以需要遍历完整棵树，递归出口就是 start == nums.length 可省略
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            // 不需要剪枝，不存在重复元素
            path.add(nums[i]);
            backtrack(result, path, nums, i+1);
            path.remove(path.size() - 1);
        }
    }
}