首页 > 代码库 > Subsets

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],
  []
]
点击打开原题链接

解法:深度搜索

class Solution 
{
public:
	vector<vector<int> > subsets(vector<int> &s) 
	{
		int len = s.size();
		sort(s.begin(),s.end());
		
		vector<int> temp;
		result.push_back(temp);
		for (int i = 1; i <=len; i++)
		{
			subsets(s,len,0,i,result,temp_result);
			
		}
		return result;
	}
	void subsets(vector<int> &s,int length, int start,int n,vector<vector<int> > &result,vector<int> &temp_result)
	{
		
		if (n == 0)
		{
			result.push_back(temp_result);
			
			return;
		}
		/*if (length -start == n)
		{
			for (int i = start; i < length; i++)
			{
				temp_result.push_back(s.at(i));
			}
		}*/
		else if (length - start >= n)
		{
			for (int i = start; i <= length -n; i++)
			{
				temp_result.push_back(s.at(i));
				subsets(s,length,i+1,n-1,result,temp_result);
				temp_result.pop_back();
				
			}
		}
		else if (length - start < n)
		{
			return;
		}
				
	}
private:
	vector<int> temp_result;
	
	vector<vector<int> > result;
};





Subsets