leetcode - Subsets

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

  class Solution {
  public:
      std::vector > subsets(std::vector &S) {
  		std::sort(S.begin(),S.end());
  		dfs(std::vector(),S,0);
  		return result;
      }
  private:
  	std::vector> result;
  	void dfs(std::vector vec, std::vector &S, int n)
  	{
  		if(n == S.size())
  		{
  			result.push_back(vec);
  			return;
  		}
  		else
  		{
  			dfs(vec,S,n+1);
  			vec.push_back(S[n]);
  			dfs(vec,S,n+1);
  		}
  	}
  };