Subsets

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

 

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const res = [];
    backtrack(res, [], nums, 0);
    return res;
};

var backtrack = function(res, path, nums, start) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
        path.push(nums[i]);
        backtrack(res, path, nums, i + 1);
        path.pop();
    }
}

We will implement a backtracking (DFS) solution. In our backtrack function, we use res to keep track of all valid subsets recorded so far, path to keep track of the current subset, nums for all the available numbers, and start for the starting index of nums that can be used (ie. nums[:start] cannot be used, as it has already been used).