題目:subsets
要求:
給定一個含不同整數的集合，返回其所有的子集 注意事項子集中的元素排列必須是非降序的，解集必須不包含重復的子集樣例:
如果 S = [1,2,3]，有如下的解：[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]算法要求:
你可以同時用遞歸與非遞歸的方式解決么？解題思路:
集合中元素的個數為n,即有2^n個子集。下面這個算法是我從一位大神那里看到的，分享一下。講一講我的理解。我這個人一般理解一段代碼，就喜歡輸出中間的數據，看看代碼運行的過程，讓我帶大家一起看一看這個算法運行的過程吧~,像我這么笨的一般就先理解，完了就死記硬背，某一天突然就想明白了~下面這個是{1,2}的子集生成過程---------------第0次j:0 k:0子集存入成功第1次j:1 k:0子集添加:1j:0 k:1子集存入成功第2次j:2 k:0j:1 k:1子集添加:2j:0 k:2子集存入成功第3次j:3 k:0子集添加:1j:1 k:1子集添加:2j:0 k:2子集存入成功---------------j跟隨著i變化，每次循環開始，j都會等于i。再看一下j的變化過程(j/=2)第一次:1~0第二次:2~1~0第三次:3~1~0而且僅當j為奇數的時候才將nums[k]添加，注意這里的k每次都自增1接著代入k來看一下(括號內為進行添加操作時k的值)第一次:1(0)~0第二次:2~1(1)~0第三次:3(0)~1(1)~0如果有第四次，那么是不是應該這樣:4~2~1(2)~0第五次:5(0)~2~1(2)~0發現沒有，這位大神巧妙的利用了操作符 "<<" 的機理，這樣的話，從0~n，j值(奇數)與k值之間的關系就巧妙的變成了子集的關系，類似于排列組合。注意每一次的結尾都為1~0,但是1的時候k的值可能不一樣，就是從第1次~第3次相當于一個循環，第2次~第4次又是一個循環，環環扣，這樣就不會出現重復的情況。接著看一下代碼理解一下。算法如下:
vector<vector<int> > subsets(vector<int> &nums) { vector<vector<int> > vecs; int n = 1 << nums.size(); int j = 0; int k = 0; for (int i = 0; i < n; i++) { j = i; k = 0; vector<int> vec; while (j) { if (j & 1) { // 這句話相當于j % 2 == 1 vec.push_back(nums[k]); } j >>= 1; // 這句話相當于j /= 2; k++; } vecs.push_back(vec); } return vecs; }
