90. 子集 II

题目链接

题目90建议结合78对比

78找子集想到两种思路：

• 1、遍历每个元素，每个元素都有两种操作方式（加入最终的子集或者不加入最终的子集）； 该思路下，每遍历一遍数组会找到一个子集。

• 2、遍历过程视为是“子集元素集合”和“待使用元素结合”之间的相互转化，每遍历到一个元 素即意味着该元素将被加入“子集元素集合”，也即找到一个子集。

思路2优于思路1，在90题目下，思路1很难去重，而思路2可以灵活的实现“树层去重”而不进行“树枝去重”。

function subsetsWithDup(nums: number[]): number[][] {
    const result: number[][] = [];
    const used: boolean[] = [];
    const sortedNums = nums.sort();
    const backtracking = (startIndex: number, nums: number[], curNodes: number[]) => {
        result.push([...curNodes]);
        if(startIndex>nums.length)return;
        for(let i=startIndex;i<nums.length;i++){
            // 去重的情况
            if(i>0 && nums[i]===nums[i-1] && !used[i-1]) continue;
            curNodes.push(nums[i]);
            used[i] = true;
            backtracking(i+1,nums,curNodes);
            used[i] = false;
            curNodes.pop();
        }
    }
    backtracking(0, sortedNums, []);
    return result;
};
console.log(subsetsWithDup([1,2,2]));
console.log(subsetsWithDup([2,2]));
console.log(subsetsWithDup([0]));