Leetcode 78/LintCode 17 - subsets

题目

Given a set of distinct integers, nums, return all possible subsets.
For example, If nums = [1,2,3], a solution is:
[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ]

要求: The solution set must not contain duplicate subsets.
可能要求：(Leetcode 没有要求但是面试可能)

• Elements in a subset must be in non-descending order.

原题链接:

Leetcode

LintCode

思路

解题方向

可以把这题想像成一个tree, 不同的subset就是不同的tree node 然后从root 开始一个一个traverse.

这样很明显的我们就可以用搜索的方法来找到答案，这里我们采用深度优先搜索（DFS）的方式

subset不能降序问题

如果题目要求不能降序 (e.g. [1,2,3] 不能 [1,3,2]) 这样我们就要在 开始搜索之前先给 nums 排一下序

去重问题

一个可能遇见的问题就是采用了重复的 subset 的情况 在 graph 的搜索里一般我们会用一个单独的 array 来存访问过的 nodes

但是这个问题我们可以使用一个 startIndex 变量来记录当前traverse 到的数字，往下的搜索会从这个数字后开始。思路和 graph 也是相似的，相当于 startIndex 之前的 nodes/nums 都已经访问过了。

这样就不会出现，比如说，在 [2,3] 然后又往回加1变成 [2,3,1] 的情况了.

实现

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    if (nums.size() == 0)
        return result;
        
    // first sort the nums
    sort(nums.begin(), nums.end());

    vector<int> subset;
    dfsHelper(0, subset, nums, result);
    return result;
}

void dfsHelper(int startIndex, 
                vector<int> & currSet, 
                vector<int> & nums,     
                vector<vector<int>> & result) {
    // add current set to result
    result.push_back(currSet);
    
    // traverse all neighbor nodes
    // use startIndex to avoid 
    // going back to previous nums 
    for (int i = startIndex; i < nums.size(); i++) {   
        // add something
        currSet.push_back(nums[i]);
        
        // recursive call
        dfsHelper(i+1, currSet, nums, result); 
        
        // remove something
        currSet.pop_back();     
    }
}

时间复杂度分析

总结

用 DFS 的时候可以参考模板，因为他们的步骤大概都是一样的

1. add current node

2. use a for loop to traverse all neighbor nodes

3. add this node to result

4. call recursive function on this node

5. remove this node

Follow-up

Leetcode 90 - subsets II