• 题目描述
• 方法1
  • 思路
  • 代码
• 方法2
  • 思路
  • 代码

题目描述

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

方法1

思路

动态规划解法:到达位置i处时，求由子列[0,i]构成的所有的子集,等于由子列[0,i-1]构成的所有子集+包含位置i处元素的所有子集,而包含位置i处元素的所有子集等于由子列[0,i-1]构成的所有子集添加元素S[i].

代码

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {

    	vector<vector<int>> ret;
    	vector<int> empty;
    	ret.push_back(empty);
    	sort(S.begin(),S.end());
    	for(int i = 0;i < S.size();i++)//动态规划，流式处理
    	{   
    		int size = ret.size();
    		for(int j = 0;j < size;j++)
    		{
    			vector<int> temp = ret[j];
    			temp.push_back(S[i]);
    			ret.push_back(temp);
    		}
    	}

    	return ret;       
    }
};

方法2

思路

按照数学中组合的思想，一个位置的处理情况：我们选取，我们不选取，我们遍历所有位置的处理情况，即得到所有的组合

代码

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) 
    {

    	vector<vector<int>> ret;
    	vector<int> temp;
        sort(S.begin(),S.end());
    	subsetsCore(S,0,ret,temp);
    	return ret;
        
    }
    
    //由于我们要求的是子集，所以必须得用temp,不能使用原数组存储信息了
    void subsetsCore(vector<int>&S,int index,vector<vector<int>>&ret,vector<int>&temp)
    {
    	if(index == S.size())
        {
            ret.push_back(temp);
    		return;
    	}
   
        temp.push_back(S[index]);
        subsetsCore(S,index+1,ret,temp);
    	temp.pop_back();
    	subsetsCore(S,index+1,ret,temp);
 
    }
};