classSolution{ public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<>(); if (candidates == null || target == 0) { return ans; }
backtrack(ans, new ArrayList<>(), candidates, target); return ans; }
publicstaticvoidbacktrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int remain){ if (remain < 0) { return; }
if (remain == 0) { res.add(new ArrayList<>(list)); return; }
int len = candidates.length; for (int i = 0; i < len; i++) { int num = candidates[i]; list.add(num); backtrack(res, list, candidates, remain - num); list.remove(list.size() - 1); } } }
Take target=7 for example, [[2,2,3],[2,3,2],[3,2,2],[7]] are the answer.
However, the correct answer is [[7],[2,2,3]].
Since it requires that each solution is not in order, so the [2,2,3] and [2,3,2] are the same answer.
What’s problem?
When and how did we duplicate the path?
Why Duplicated?
At each node of the tree, all the candidates were searched and used, so there is a duplicate list.
Is it possible to deduplicate while searching?
Of course we can.
We have to search the elements in order while searching, since the output is not by order. We search from the certain position in the next round.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
publicstaticvoidbacktrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int start, int remain){ if (remain < 0) { return; }
if (remain == 0) { res.add(new ArrayList<>(list)); return; }
int len = candidates.length; for (int i = start; i < len; i++) { int num = candidates[i]; list.add(num); backtrack(res, list, candidates, i, remain - num); list.remove(list.size() - 1); } }
By now we deduplicating it and complete the problem.
Pruning
We can prune the tree to make it work more efficiency.
classSolution{ public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<>(); if (candidates == null || target == 0) { return ans; }
Arrays.sort(candidates); backtrack(ans, new ArrayList<>(), candidates, 0, target); return ans; }
publicstaticvoidbacktrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int begin, int remain){ if (remain < 0) { return; }
if (remain == 0) { res.add(new ArrayList<>(list)); return; }
int len = candidates.length; for (int i = begin; i < len; i++) { int num = candidates[i]; if (remain - num < 0) { break; } list.add(num); backtrack(res, list, candidates, i, remain - num); list.remove(list.size() - 1); } } }
Analysis
Time Complexity: O(Sum), Sum is all the path.
Space Complexity: O(target).
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)