学步园

Combinations:

Given two integers n and k,
return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k =
2, a solution is:

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

#define vi vector<int> 
#define vvi vector<vi >
#define pb push_back


class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        vvi ret;
	    vi had;
	    solve(1,n,k,ret,had);
	    return ret;
    }
    void solve(int c,int n,int k,vvi& ret,vi& had)
    {
	    if ( k<=0||c>n )
	    {
		    if (k==0)
			    ret.pb(had);
		    return;
	    }
	    had.pb(c);
	    solve(c+1,n,k-1,ret,had);
	    had.pop_back();
	    solve(c+1,n,k,ret,had);
    }
	    
};

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

#define vi vector<int> 
#define vvi vector<vi >
#define pb push_back
#define viter vi::iterator

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        sort(S.begin(),S.end());
	    viter r= unique(S.begin(),S.end());
	    viter l=S.begin();
	    vvi ret;
	    vi had;
	    solve(l,r,ret,had);
	    return ret;
    }
    void solve(viter l,viter r,vvi& ret,vi& had)
    {
	    if ( l==r )
	    {
		    ret.pb(had);
		    return;
	    }
	    viter t=l++;
	    solve(l,r,ret,had);
	    had.pb(*t);
	    solve(l,r,ret,had);
	    had.pop_back();
    }
};

Subsets II：

Given a collection of integers that might contain duplicates, 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,2],
a solution is:

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

剪掉重复结果的思路同Combination Sum II 一样。

#define vi vector<int>
#define vvi vector<vi >
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    		int n=S.size();
			vi had;
			vvi ans;
			sort(S.begin(),S.end());
			solve(0,S,had,ans,0);
			return ans;
	}
	void solve(int k,vi& S, vi& had,vvi& ans, int used)
	{
			int n=S.size();
			if ( k>=n )
			{
					ans.push_back(had);
					return;
			}
			solve(k+1,S,had,ans,0);
			if ( k==0 || S[k]!=S[k-1] || used==1 )
			{
					had.push_back(S[k]);
					solve(k+1,S,had,ans,1);
					had.pop_back();
			}
    }
};