Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Subsets

Leetcode algorithms 第 78 题:Subsets。

题目

Given a set of distinct integers, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解答

求n个数的所有子集,使用递归算法,从最小的开始选择,每次从剩下的数字中选择一个,然后下次从该数字的后面的数字进行选择,直到没有数字可以选为止。

注意递归的每一次都可以得到一个子集。

具体代码如下:

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > ans;
        vector<int> cur;
        sort(S.begin(), S.end());
        subsets(0, cur, S, ans);
        return ans;
    }
    void subsets(int id, vector<int> &cur, vector<int> &S, vector<vector<int> > &ans)
    { //当前可以选择的最小数,当前已选择的数字,给定的数组,答案
        ans.push_back(cur); //得到一个子集
        for (int i = id; i < S.size(); i++) 
        {
            cur.push_back(S[i]); //选择下一个数字
            subsets(i+1, cur, S, ans);
            cur.pop_back(); //回溯
        }
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论