LeetCode 78. Subsets (javascript)

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.

Idea:

DFS(Depth First Search)

DFS Template:

function dfs(nums, n, start, cur, res...) {
    if (exit recursive condition) {
        // record answer
        return;
    }
    for (possible solution) {
        // modify current state
        dfs(nums, n, i + 1, cur, res...);
        // recover current state

    }
    return something if need // option
};

Solution:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let cur = [];
    let res = [];
    for (let i = 0; i <= nums.length; i++) {
        dfs(nums, i, 0, cur, res);
    }
    return res;
};

var dfs = function(nums, n, start, cur, res) {
    // exit recursive condition
    if (cur.length === n) {
        // record answer
        res.push(cur.concat());
        return;
    }
    
    // possible solution
    for (let i = start; i < nums.length; i++) {
        // modify current state
        cur.push(nums[i]);
        dfs(nums, n, i + 1, cur, res);
        // recover current state
        cur.pop();
    }
};