Backtracking to solve subset problem

1. A subset of （leetcode78）

nums Elements do not repeat

There are no termination conditions 、path Update on push Into the res in

var subsets = function(nums) {
    let res = [],path= [];
    function backtracking(startIndex){
        res.push([...path]);
        for(let i = startIndex;i<nums.length;i++){
            path.push(nums[i]);
            backtracking(i+1);
            path.pop();
        }
    }
    backtracking(0);
    return res;
};

---

2. A subset of II（leetcode90）

nums Elements repeat , It is required that the subset is not repeated

duplicate removal ： Use used, De duplication of tree layer

var subsetsWithDup = function(nums) {
    nums.sort((a,b)=>a-b);
    let used = new Array(nums.length).fill(false);
    let res = [],path=[];
    function backtracking(startIndex){
        res.push([...path]);
        for(let i = startIndex;i<nums.length;i++){
            if(i>0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            if (used[i] == true) continue;
            path.push(nums[i]);
            used[i] = true;
            backtracking(i+1);
            path.pop();
            used[i] = false;
        }
    }
    backtracking(0);
    return res;
};

---

3. Increasing subsequence （leetcode491）

Increasing subsequence

Output ： Increasing subsequence in array

Be careful ： There may be duplicate elements in the array , So be right path Deduplication , Use used Can also be , Use set Can also be

var findSubsequences = function(nums) {
    let res = [],path = [];
    const set = new Set();
    function backtracking(startIndex){
        if(path.length > 1){
            // path Array , Convert to string 
            const str = path.toString();
            if(!set.has(str)){
                res.push([...path]);
                set.add(str);
            }
        }
        for(let i = startIndex;i<nums.length;i++){
            if(path.length == 0 || path[path.length-1]<=nums[i]){
                path.push(nums[i]);
                backtracking(i+1);
                path.pop();
            }
        }
    }
    backtracking(0);
    return res;
};