Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { const size_t n = nums.size(); vector<int> v; vector<vector<int> > result; for (int i = 0; i < 1<<n; ++i) { for (int j = 0; j < n; ++j) { if(i & 1 << j) v.push_back(nums[j]); } result.push_back(v); v.clear(); } return result; } };
3ms
迭代,增量构造.没看懂
http://www.cnblogs.com/TenosDoIt/p/3451902.html
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); vector<vector<int> > result(1); for (auto elem : S) { result.reserve(result.size() * 2); auto half = result.begin() + result.size(); copy(result.begin(), half, back_inserter(result)); for_each(half, result.end(), [&elem](decltype(result[0]) &e){ e.push_back(elem); }); } return result; } };
3ms
位向量法
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); } };
6ms
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); // vector<vector<int> > result; vector<int> path; subsets(S, path, 0, result); return result; } private: static void subsets(const vector<int> &S, vector<int> &path, int step, vector<vector<int> > &result) { if (step == S.size()) { result.push_back(path); return; } //S[step] subsets(S, path, step + 1, result); //S[step] path.push_back(S[step]); subsets(S, path, step + 1, result); path.pop_back(); } };
6ms
Iterative This problem can also be solved iteratively. Take [1, 2, 3] in the problem statement as an example. The process of generating all the subsets is like: Initially: [[]] Adding the first number to all the existed subsets: [[], [1]]; Adding the second number to all the existed subsets: [[], [1], [2], [1, 2]]; Adding the third number to all the existed subsets: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]. Have you got the idea :-) The code is as follows. class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> subs(1, vector<int>()); for (int i = 0; i < nums.size(); i++) { int n = subs.size(); for (int j = 0; j < n; j++) { subs.push_back(subs[j]); subs.back().push_back(nums[i]); } } return subs; } };
1 // Recursion. 2 class Solution { 3 public: 4 vector<vector<int> > subsets(vector<int> &S) { 5 vector<vector<int> > res; 6 vector<int> out; 7 sort(S.begin(), S.end()); 8 getSubsets(S, 0, out, res); 9 return res; 10 } 11 void getSubsets(vector<int> &S, int pos, vector<int> &out, vector<vector<int> > &res) { 12 res.push_back(out); 13 for (int i = pos; i < S.size(); ++i) { 14 //if (i != pos && S[i] == S[i-1]) continue;//subsets II 15 out.push_back(S[i]); 16 getSubsets(S, i + 1, out, res); 17 out.pop_back(); 18 //while (S[i] == S[i + 1]) ++i; //subsets II 19 } 20 } 21 };
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { sort(S.begin(), S.end()); // ???? vector<vector<int> > result; vector<int> path; dfs(S, S.begin(), path, result); for (int i = 0; i < result.size(); ++i) { for (int j = 0; j < result[i].size(); ++j) { printf("%d ", result[i][j]); }printf(" "); } return result; } private: static void dfs(const vector<int> &S, vector<int>::iterator start, vector<int> &path, vector<vector<int> > &result) { result.push_back(path); printf("@@@@@@@@@@Line:%d start:%d ", __LINE__, *start); for (auto i = start; i < S.end(); i++) { printf("i:%d ", *i); if (i != start && *i == *(i-1)) { printf("Continue****LINE:%d start:%d i:%d ", __LINE__, *start, *i); continue; } path.push_back(*i); dfs(S, i + 1, path, result); for(auto xx : path) printf("BEFORE:%d ", xx); printf(" LINE:%d start:%d i:%d ", __LINE__, *start, *i); path.pop_back(); for (auto xx : path) printf("AFTER:%d ", xx); printf(" "); } } }; int main(int argc, char *argv[]) { vector<int> v{1,2,2}; Solution sn; sn.subsetsWithDup(v); //printf("%d %d ",v[0],v.size()); return 0; }
This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.
Subsets : https://leetcode.com/problems/subsets/
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){ list.add(new ArrayList<>(tempList)); for(int i = start; i < nums.length; i++){ tempList.add(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.remove(tempList.size() - 1); } }
Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/
public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){ list.add(new ArrayList<>(tempList)); for(int i = start; i < nums.length; i++){ if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates tempList.add(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.remove(tempList.size() - 1); } }
Permutations : https://leetcode.com/problems/permutations/
public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<>(); // Arrays.sort(nums); // not necessary backtrack(list, new ArrayList<>(), nums); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){ if(tempList.size() == nums.length){ list.add(new ArrayList<>(tempList)); } else{ for(int i = 0; i < nums.length; i++){ if(tempList.contains(nums[i])) continue; // element already exists, skip tempList.add(nums[i]); backtrack(list, tempList, nums); tempList.remove(tempList.size() - 1); } } }
Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/
public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){ if(tempList.size() == nums.length){ list.add(new ArrayList<>(tempList)); } else{ for(int i = 0; i < nums.length; i++){ if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue; used[i] = true; tempList.add(nums[i]); backtrack(list, tempList, nums, used); used[i] = false; tempList.remove(tempList.size() - 1); } } }
Combination Sum : https://leetcode.com/problems/combination-sum/
public List<List<Integer>> combinationSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, target, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){ if(remain < 0) return; else if(remain == 0) list.add(new ArrayList<>(tempList)); else{ for(int i = start; i < nums.length; i++){ tempList.add(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements tempList.remove(tempList.size() - 1); } } }
Combination Sum II (can't reuse same element) : https://leetcode.com/problems/combination-sum-ii/
public List<List<Integer>> combinationSum2(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, target, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){ if(remain < 0) return; else if(remain == 0) list.add(new ArrayList<>(tempList)); else{ for(int i = start; i < nums.length; i++){ if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates tempList.add(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i + 1); tempList.remove(tempList.size() - 1); } } }
Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/
public List<List<String>> partition(String s) { List<List<String>> list = new ArrayList<>(); backtrack(list, new ArrayList<>(), s, 0); return list; } public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){ if(start == s.length()) list.add(new ArrayList<>(tempList)); else{ for(int i = start; i < s.length(); i++){ if(isPalindrome(s, start, i)){ tempList.add(s.substring(start, i + 1)); backtrack(list, tempList, s, i + 1); tempList.remove(tempList.size() - 1); } } } } public boolean isPalindrome(String s, int low, int high){ while(low < high) if(s.charAt(low++) != s.charAt(high--)) return false; return true; }
/*Without any crap! Hit the road! Since we have to collect all the possible sets that meet the requirements -> a palindrome; so traversing the whole possible paths will be definitely the case -> using DFS and backtracking seems to be on the table. try from the start index of the string till any index latter and then check its validity - a palindrome? from the start index till the ending? if so, we need to store it in a stack for latter collection and then traverse further starting from the previous ending index exclusively and begin the checking again and on and on till the start index is beyond the string; at that time we are to collect the palindromes along the paths. Several stuff should be specified: checking whether a string is palindrome is quite simple in C using pointer; using DP might not help a lot since the checking process is quite fast while DP will require extra work to record and space allocation and so on. In the end, let's check its space and time consumption: space cost O(n*2^n) -> one set of palindrome will take about O(n) but the amount of sets is dependent on the original string itself. time cost O(n*2^n) -> collecting them while using the space to store them so the space and time cost should be linearly proportional; since the range can be varied a lot depending on the actual provided string so the performance might not be a problem. by LHearen
4ms in us. 72ms in cn. */ void traverse(char* s, int len, int begin, char** stack, int top, char**** arrs, int** colSizes, int* returnSize) { if(begin == len) //there is nothing left, collect the strings of a set; { *returnSize += 1; *colSizes = (int*)realloc(*colSizes, sizeof(int)*(*returnSize)); int size = top+1; (*colSizes)[*returnSize-1] = size; *arrs = (char***)realloc(*arrs, sizeof(char**)*(*returnSize)); (*arrs)[*returnSize-1] = (char**)malloc(sizeof(char*)*size); for(int i = 0; i < size; i++) (*arrs)[*returnSize-1][i] = stack[i]; return ; } for(int i = begin; i < len; i++) //check each string that begin with s[begin]; { int l=begin, r=i; while(l<r && s[l]==s[r]) l++, r--; if(l >= r) //it's a palindrome; { int size = i-begin+1; char *t = (char*)malloc(sizeof(char)*(size+1)); *t = '