# missjing/leetcode

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
81 lines (74 sloc) 1.83 KB
 problem: 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], [] ] ---------------------------------------------------------------- solution: 排列组合中的排列问题。 //思路一、二进制法。题目要求结果组合中数字按升序排列，因此刚开始需对数组排序。 vector > subsets(vector &S) { vector > ret; int n = S.size(); if(n == 0) return ret; sort(S.begin(), S.end()); int maxNum = 1 << n; for(int i = 0; i < maxNum; ++i) { vector subset; int idx = 0; int j = i; while(j > 0) { if(j & 1) subset.push_back(S[idx]); j = j >> 1; ++idx; } ret.push_back(subset); } return ret; } //思路二、标志位法。题目要求结果组合中数字按升序排列，因此刚开始需对数组排序。 void subsets_aux(int idx, vector &S, vector > &ret, vector &isVisited) { if(idx == S.size()) { vector tmp; for(int i = 0; i < S.size(); ++i) { if(isVisited[i]) tmp.push_back(S[i]); } ret.push_back(tmp); return; } isVisited[idx] = true; subsets_aux(idx + 1, S, ret, isVisited); isVisited[idx] = false; subsets_aux(idx + 1, S, ret, isVisited); } vector > subsets(vector &S) { vector > ret; if(S.size() == 0) return ret; sort(S.begin(), S.end()); vector isVisited(S.size(), false); subsets_aux(0, S, ret, isVisited); return ret; }