Subsets I

Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,If nums = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]
这个是最原始的回溯问题
从数组第一个元素开始遍历，每遍历到一个新的元素就和已有的所有结果分别加在一起，作为新的结果。
比如[1,2,3,4]
[[]]
遍历到1，新加入[1]
[[],[1]]
遍历到2，新加入[2],[1,2]
[[],[1],[2],[1,2]]
遍历到3，新加入[3],[1,3],[2,3],[1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
遍历到4，新加入[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]

var subsets = function(nums) {
    var res = [[]];
    for (var i = 0;i < nums.length;i++) {
        var now = nums[i];
        var temp = [];
        for (var j = 0;j < res.length;j++) {
            var newres = res[j].concat();
            newres.push(now);
            temp.push(newres);
        }
        for (j = 0;j < temp.length;j++){
            res.push(temp[j]);
        }
    }
    return res;
};

Subsets II

这次给的数组可能是有重复元素的，但是最后的结果不能有重复的。
对上面的算法稍加修改即可，首先要排序，排序的顺序没有关系，只要保证排序完成时重复的元素在一起就行。
对于每一个与之前元素重复的元素，只针对上一个元素新生成的结果继续生成新结果，而上一个元素生成的结果之前的结果，这次就不遍历了，例子：[1,2,2,2]
[]
遍历1
[]
[1]
遍历2
[]
[1]
[2]
[1,2]
遍历2，由于与前面元素相同，[]，[1]都不须再生成了，只基于[2],[1,2]继续生成
[]
[1]
[2]
[1,2]
[2,2]
[1,2,2]
遍历2，同理，只基于[2,2],[1,2,2]继续生成
[]
[1]
[2]
[1,2]
[2,2]
[1,2,2]
[2,2,2]
[1,2,2,2]

var subsetsWithDup = function(nums) {
    nums.sort();
    var res = [[]];
    var diff = 0;
    for (var i = 0;i < nums.length;i++) {
        var now = nums[i];
        var offset = res.length;
        if (now===nums[i-1])
            offset = diff;
        var temp = [];
        for (var j = res.length - offset;j < res.length;j++) {
            var newres = res[j].concat();
            newres.push(now);
            temp.push(newres);
        }
        //res.push([now]);
        diff = temp.length;
        for (j = 0;j < temp.length;j++){
            res.push(temp[j]);
        }
    }
    return res;
};