DataStructure_Algorithm_HandBook_PreForLeetCode

78. Subsets

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

这道题目和之前的回溯不一样的点在于，不需要累加等于某个和，也不需要特定的长度，就是子集，因此子集就是不用限制长度，但是从 i 的位置开始，由于不能重复，就一直往后选就可以了。

var subsets = function(nums) {
    let result = [];
    dfs(0,[],nums,result);
    return result; 
};
function dfs(index,path,nums,result){
    
    //因为第一次的时候 path 为空，直接加，所以空集也在里面 
    result.push([...path]);
    //不需要任何的限制，因此只有说 index 走到最后的时候才加进去
    if(index === nums.length) return; 

    for(let i = index; i < nums.length; i++){
        path.push(nums[i]);
        dfs(i+1,path,nums,result);
        path.pop();
    }
}