leetcode: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],
  []
]      

題目位址： https://oj.leetcode.com/problems/subsets/

解題思路：

這道題做了兩種解法。

解法1：

因為從S中每添加一個元素進來，下一層的集合=上一層的集合+每一個上一層的集合的後面加上新添加的那個元素。如下：

0----------[ ]

1----------[ ] [1]

2----------[ ] [1] [2] [1 2]

3----------[ ] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3]

.........

代碼：

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(),S.end());
		
		vector<vector<int> > ret(1);
		for(int i=0;i<S.size();i++){
			int len=ret.size();

			for(int j=0;j<len;j++){
				vector<int> tmp=ret[j];
				tmp.push_back(S[i]);
				ret.push_back(tmp);
			}
		}
		return ret;
    }
};
           

解法2：

用遞歸+回溯的方法，這個方法可能看代碼會比較清晰。參考了别人的代碼：

class Solution {
public:
	vector<vector<int> > ret;
    vector<vector<int> > subsets(vector<int> &S) {
        ret.clear();
		sort(S.begin(),S.end());

		vector<int> tmpans;
		dfs(S,0,tmpans);
		return ret;
    }
private:
	void dfs(vector<int> &s,int loc,vector<int> &tmp){
		if(loc==s.size()){
			ret.push_back(tmp);
			return;
		}
		
		tmp.push_back(s[loc]);
		dfs(s,loc+1,tmp);
		tmp.pop_back();
		dfs(s,loc+1,tmp);
	}
};