Subsets#

Given an array of integers nums without duplicates, return all possible subsets (the power set) of the array.
Note: The solution set must not contain duplicate subsets.

Example#

Solution#

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    var target = [[]];
    var n = nums.length;
    if(!n) return target;
    var dfs = (cur, tmp ,deep, limit) => {
        if (tmp.length + (n - cur + 1) < limit) return void 0;
        if(limit === deep) {
            target.push(tmp);
            return void 0;
        }
        for(let i=cur;i<n; ++i){
            dfs(i+1, [...tmp, nums[i]], deep+1, limit);
        }
    }
    nums.forEach((v,i) => dfs(0, [], 0, i+1));
    return target;
};

/**
    dfs(i+1, [...tmp, nums[i]], deep+1, limit);
        1         2          3
      2   3       3      
    ...   ...    ...
    dfs(cur+1, [...tmp, nums[i]], deep+1, limit);
        1         2          3
      2   3     2   3      2   3 
     ... ...   ... ...    ...  ...
 */

Idea#

Essentially, this is a combination problem. Taking an array of length 4 like [1, 2, 3, 4] and combining 2 values as an example, for every two elements, we can form an array like [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], and [3, 4]. Following this logic, we need to extract subsets of lengths 1 to length from the given array. First, we define the target array which will include an empty array, signifying all arrays are subsets of themselves. We then calculate the length n of the input array. If the length is 0, we return the target array. We then define a recursive function to traverse the depths of the problem. First, we perform pruning. If the size of the current tmp array is s and the length of the undecided interval [cur,n] is t, if s + t < limit, even if all t elements are selected, it is impossible to construct a sequence of length limit. Hence, there is no need to continue recursion in this case. We then check if the recursion depth equals limit, and if so, we add the tmp array to the target array and return. Next, we define a loop from cur to n, and pass a new array constructed from tmp with cur to the next recursion. Finally, we define a loop to get the length of the subset array to be obtained, start the recursion, initialize cur as 0, deep as 0, tmp as an empty array, and limit as i+1. After the recursion is completed, the target array is returned.

Daily Question#

Reference#