Subsets [source code]
public class Subsets {
static
/******************************************************************************/
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<> ();
dfs (nums, 0, res, new ArrayDeque<Integer> ());
return res;
}
void dfs (int[] nums, int index, List<List<Integer>> lss, Deque<Integer> accum) {
if (index >= nums.length) {
lss.add (new ArrayList<> (accum));
return;
}
dfs (nums, index + 1, lss, accum);
accum.push (nums[index]);
dfs (nums, index + 1, lss, accum);
accum.pop ();
}
}
/******************************************************************************/
public static void main(String[] args) {
Subsets.Solution tester = new Subsets.Solution();
}
}
应该说这个题目思路还是不难的, 就是要思考在每一个iteration你只有一个binary的decision, 对于当前的位置, 要还是不要; 然后backtracking的一些细节搞好就行了; 最后的速度是4ms (11%), 老题了, 还能接受的速度;
注意我这里Deque的运用; 因为这个操作更加方便;
另外, 这个题目还有一个思路就是用之前bit枚举的思路, 因为求power set本来的思路就是给每一个entry一个binary的yes or no的bit; 所以直接就是从0开始枚举二进制就行了; 不过这个方法的短处以前也见到过, 就是最多只能处理32位, 或者用long的话, 或许是64位, 但是还是有限制;
没有editorial;
要知道, 我上面的这个算法是不难改写成一个不需要helper的recursion算法的, 这里discussion的一个解法, 就是用的类似的思路, 不过他没有用recursion来做:
public List<List<Integer>> subsets(int[] S) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>());
Arrays.sort(S);
for(int i = S.length - 1; i >= 0; i--){
int size = res.size() - 1;
for(int j = size; j >= 0; j--){
List<Integer> newList1 = new ArrayList<>();
newList1.add(S[i]);
newList1.addAll(res.get(j));
res.add(newList1);
}
}
return res;
}
刚开始没有看出来, 笔算了一下1,2,3之后还是看懂了(笔算的trace记得用有tree结构的表格来记录变量的值, 一个iteration首先肯定要包含before the iteration时刻的值, 然后可以选择性的包含一点其他时刻的值); 思路还是很直接的; 速度也比我自己的这个DFS要快哦; 当然也可能是波动;
discussion最优解是一个对backtracking的总结:
@issac3 said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
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/][1]
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/][2]
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/][3]
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/][4]
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/][5]
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/][6]
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/][7]
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; }[1]: https://leetcode.com/problems/subsets/
[2]: https://leetcode.com/problems/subsets-ii/
[3]: https://leetcode.com/problems/permutations/
[4]: https://leetcode.com/problems/permutations-ii/
[5]: https://leetcode.com/problems/combination-sum/
总体感觉还可以; 不过就算是单看这一题, 也可以看到这个人的代码结构跟我还是有点区别的; 我不太喜欢他这个backtracking的结构, 感觉没有一个明确的逻辑结构在里面, 而且你看他在DFS之前还要先sort一下, 我认为可能就跟他这个算法的问题有关;
不对, 看了一下下面的评论, 这个sort的原因是这个:
@leixinyuethu said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
@bargitta
You can see this link:https://web.archive.org/web/20160405044050/https://leetcode.com/problems/subsets/
This problem had a note:Elements in a subset must be in non-descending order.
But now this note is deleted. So you do not have to sort first.
所以他这个算法本身是没有问题的;
这个是一个人画的trace:
@JeremyDeng said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
I drew an ugly but clear pic about how backtracking works. Once nums[i] arrived at end, remove the last element and go back to last level until all possible solutions are stored.
这个trace看完大概就可以很declarative的来解释这个算法的思路了, 这个人的思路就是每一个depth(level), 向path里面添加一个element; 而iteration里面的这个循环, 就是一个挑选的作用; 注意他这个做法跟我的做法的一个很大的不同在于, 他在每一个node都要add一次result, 而我的add只发生在最后的leaf level;
事实上, 这个算法好像比我想的要复杂一些, 因为你要看到, 他这个算法也是做到了自动去重的; 后来仔细看了一下这个trace, 我发现, 在level1的时候, 你做的工作其实是choose the 1st element for the subset; 因为你如果比如level1选择了i, 那么往下的所有level都不能选择include0..i-1范围内的element了; 这个好像就是他这个方法里面enforce order的做法; 不停的移动可选范围的起点(向右选择); 并没有明确的对size进行一个限定, 最后被add的subset的size是自动被管理的;
另外, 也有人就是用我这个思路来做的:
@ZZJJ said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
Nice Summary !
I think below part is difficult to reason about it's runetime peformance, the for loop make things complicated.
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
Rather, this kind of code seems simpler for me:
public List<List<Integer>> subsets(int[] ns) {
List<List<Integer>> acc = new ArrayList<>();
recur(acc, ns, new Stack<>(), 0);
return acc;
}
private void recur(List<List<Integer>> acc, int [] ns, Stack path, int start){
if(ns.length == start){
acc.add(new ArrayList<>(path));
return;
}
// take ns[start]
path.push(ns[start]);
recur(acc, ns, path, start + 1);
path.pop();
// dont take ns[start]
recur(acc, ns, path, start + 1);
}
这个基本就是我的做法了; 复杂度确实是很好分析, 一共就只有N个level, 每一个level的fanning是2, 所以最后就是一个2^N, 这个也是符合最后的powerset的size的;
bit做法, 居然AC了, 看来这个题目的case没有故意恶心人:
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort (S.begin(), S.end());
int elem_num = S.size();
int subset_num = pow (2, elem_num);
vector<vector<int> > subset_set (subset_num, vector<int>());
for (int i = 0; i < elem_num; i++)
for (int j = 0; j < subset_num; j++)
if ((j >> i) & 1)
subset_set[j].push_back (S[i]);
return subset_set;
}
};
底下的一个解释:
@leet_nik said in My solution using bit manipulation:
This is an amazing solution.Learnt a lot.Let me try to explain this to those who didn't get the logic. Number of subsets for {1 , 2 , 3 } = 2^3 . why ? case possible outcomes for the set of subsets 1 -> Take or dont take = 2 2 -> Take or dont take = 2 3 -> Take or dont take = 2 therefore , total = 2*2*2 = 2^3 = { { } , {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} } Lets assign bits to each outcome -> First bit to 1 , Second bit to 2 and third bit to 3 Take = 1 Dont take = 0 0) 0 0 0 -> Dont take 3 , Dont take 2 , Dont take 1 = { } 1) 0 0 1 -> Dont take 3 , Dont take 2 , take 1 = {1 } 2) 0 1 0 -> Dont take 3 , take 2 , Dont take 1 = { 2 } 3) 0 1 1 -> Dont take 3 , take 2 , take 1 = { 1 , 2 } 4) 1 0 0 -> take 3 , Dont take 2 , Dont take 1 = { 3 } 5) 1 0 1 -> take 3 , Dont take 2 , take 1 = { 1 , 3 } 6) 1 1 0 -> take 3 , take 2 , Dont take 1 = { 2 , 3 } 7) 1 1 1 -> take 3 , take 2 , take 1 = { 1 , 2 , 3 } In the above logic ,Insert S[i] only if (j>>i)&1 ==true { j E { 0,1,2,3,4,5,6,7 } i = ith element in the input array } element 1 is inserted only into those places where 1st bit of j is 1 if( j >> 0 &1 ) ==> for above above eg. this is true for sl.no.( j )= 1 , 3 , 5 , 7 element 2 is inserted only into those places where 2nd bit of j is 1 if( j >> 1 &1 ) == for above above eg. this is true for sl.no.( j ) = 2 , 3 , 6 , 7 element 3 is inserted only into those places where 3rd bit of j is 1 if( j >> 2 & 1 ) == for above above eg. this is true for sl.no.( j ) = 4 , 5 , 6 , 7 Time complexity : O(n*2^n) , for every input element loop traverses the whole solution set length i.e. 2^n
一个总结, 其实没有什么新货:
@jianchao.li.fighter said in C++ Recursive/Iterative/Bit-Manipulation Solutions with Explanations:
Recursive (Backtracking)
This is a typical problem that can be tackled by backtracking. Since backtracking has a more-or-less similar template, so I do not give explanations for this method.
class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> subs; vector<int> sub; genSubsets(nums, 0, sub, subs); return subs; } void genSubsets(vector<int>& nums, int start, vector<int>& sub, vector<vector<int>>& subs) { subs.push_back(sub); for (int i = start; i < nums.size(); i++) { sub.push_back(nums[i]); genSubsets(nums, i + 1, sub, subs); sub.pop_back(); } } };
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:
[object Object]- 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; } };
Bit Manipulation
This is the most clever solution that I have seen. The idea is that to give all the possible subsets, we just need to exhaust all the possible combinations of the numbers. And each number has only two possibilities: either in or not in a subset. And this can be represented using a bit.
There is also another a way to visualize this idea. That is, if we use the above example,
1appears once in every two consecutive subsets,2appears twice in every four consecutive subsets, and3appears four times in every eight subsets, shown in the following (initially the8subsets are all empty):
[], [], [], [], [], [], [], []
[], [1], [], [1], [], [1], [], [1]
[], [1], [2], [1, 2], [], [1], [2], [1, 2]
[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]The code is as follows.
class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { sort(nums.begin(), nums.end()); int num_subset = pow(2, nums.size()); vector<vector<int> > res(num_subset, vector<int>()); for (int i = 0; i < nums.size(); i++) for (int j = 0; j < num_subset; j++) if ((j >> i) & 1) res[j].push_back(nums[i]); return res; } };
Well, just a final remark. For Python programmers, this may be an easy task in practice since the
itertoolspackage has a functioncombinationsfor it :-)
submission基本是波动;
Problem Description
Given a set of distinct integers, nums, return all possible subsets (the power set).
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],
[]
]
Difficulty:Medium
Total Accepted:210.2K
Total Submissions:483.5K
Contributor:LeetCode
Companies
facebookamazonbloombergubercoupang
Related Topics
arraybacktrackingbit manipulation
Similar Questions
Generalized Abbreviation