Given a set of distinct integers, S, return all possible subsets.
Note:
For example,
If S = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
Array Backtracking Bit Manipulation
class Solution { vector<vector<int> > m_res; vector<int> m_array; public: void dfs(int n, int k, int start, vector<int> & in) { if(k == m_array.size()) { m_res.push_back(m_array); return; } for(int i = start; i < n; i++) { m_array.push_back(in[i]); dfs(n, k, i + 1, in); m_array.pop_back(); } } void combine(int n, int elementNum, vector<int> & in) { dfs(n, elementNum, 0, in); } public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); for(int i = 0; i <= S.size(); i++) { combine(S.size(), i, S); m_array.clear(); } return m_res; } };
思路二：也可以直接dfs，对于每一个元素都有2种选择，加入或者不加入，其实dfs的关键就是在dfs中的loop是每个元素可以选择的范围，对于这个题目，就是要么加入，要么不加入，可以用for（i=0；i<2;i++）表示。其实就是标准的回溯法子集树问题。
class Solution { vector<vector<int> > m_res; vector<int> m_array; public: void dfs(int dep, vector<int> &S) { if(dep == S.size()) { m_res.push_back(m_array); return ; } #if 0 for(int i = 0; i< 2; i++) { // contain the element if(i == 0) { m_array.push_back(S[dep]); dfs(dep + 1, S); m_array.pop_back(); } // don‘t contain the element else dfs(dep + 1, S); } #else // contain the element m_array.push_back(S[dep]); dfs(dep + 1, S); m_array.pop_back(); // don‘t contain the element dfs(dep + 1, S); #endif } vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); dfs(0, S); return m_res; } };
思路3.位向量法，和上面的方法没有本质区别
// LeetCode, Subsets // Î位向量法，深搜，时间复杂度 O(2^n)，空间复杂度 O(n) class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); // Êä³öÒªÇóÓÐÐò vector<vector<int> > result; vector<bool> selected(S.size(), false); subsets(S, selected, 0, result); return result; } private: static void subsets(const vector<int> &S, vector<bool> &selected, int step, vector<vector<int> > &result) { if (step == S.size()) { vector<int> subset; for (int i = 0; i < S.size(); i++) { if (selected[i]) subset.push_back(S[i]); } result.push_back(subset); return; } // 不选 S[step] selected[step] = false; subsets(S, selected, step + 1, result); // 选 S[step] selected[step] = true; subsets(S, selected, step + 1, result); } };
原文：http://www.cnblogs.com/diegodu/p/4335412.html