http://blog.csdn.net/ojshilu/article/details/19432465
comments:
I 这个tricky是从后向前。 9没选{}.9选了 {9} II 8之后9没选{8},9选了{8,9} III.1 7,之后8没选，然后9没选。8没选，9选了 III.2 7之后8选了 既情况II
前面k个都是不选的，后面是不选和选都有的两种情况。当n=all的时候，每个数都被确定了选择or不选，所以数列确定。输出。
可以加debug log。print n=1不选.数列。 n=1选数列. 将不选的位置，如A[0]=-1,代替。选的位置，用数字代替-----------pending
每个now表示的是一个子集，所以用vector。如now是{(1)} ， {(1) (2)}, {(0),(2)}......
==============================================================================
典型的递归状态生成问题。类似于全排列的生成问题。
问题一：无重复元素集合的子集。Given a set of distinct integers, S, return all possible subsets.
思路：借助一个now数组存储临时的子集。不断切换状态进行深层递归，在递归最深处保存生成的子集。
[cpp] view plain copy class Solution { public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > result; if(S.empty()) return result; sort(S.begin(), S.end()); vector<int> now; fun(S, result, now, 0); return result; } void fun(const vector<int> &s, vector<vector<int> > &result, vector<int> &now, int n) { if(n == s.size()) { result.push_back(now); //递归最深处：所有元素都判定过取或不取 return; } else { fun(s, result, now, n+1); //不取 now.push_back(s[n]); fun(s, result, now, n+1); //取 now.pop_back(); //回溯前一定要恢复回原样 } } };
问题二：有重复元素集合的子集。Given a collection of integers that might contain duplicates, S, return all possible subsets.
[cpp] view plain copy class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int> > result; vector<int> now; sort(S.begin(), S.end());//排序 set<vector<int> > s; backtrack(s, now, S, 0); set<vector<int> >::iterator it = s.begin(); for(;it != s.end();it++) result.push_back(*it); return result; } void backtrack(set<vector<int> > &result, vector<int> &now, vector<int> &S, int idx) { if(idx == S.size()) { result.insert(now);//set去重复 return; } backtrack(result, now, S, idx+1); now.push_back(S[idx]); backtrack(result, now, S, idx+1); now.pop_back(); } };
