五刷 06/2022
Version #1 DFS with Backtracking
Time O(N * 2^N) -> 2^N to exhaust all combinations, and N to deep copy the path list
Space O(N) -> depth of the tree
Runtime: 5 ms, faster than 70.80% of Java online submissions for Combination Sum II.
Memory Usage: 42.3 MB, less than 97.79% of Java online submissions for Combination Sum II.
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return result;
}
// sort in order to guarantee that the same number won't be added multiple times at the same layer
Arrays.sort(candidates);
dfs(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private void dfs(int[] candidates, int target, int startIndex, List<Integer> path, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(path));
return;
}
if (target < 0) {
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (i != startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
path.add(candidates[i]);
dfs(candidates, target - candidates[i], i + 1, path, result);
path.remove(path.size() - 1);
}
}
}
四刷
05/21/2021
一遍就过了
Runtime: 2 ms, faster than 98.71% of Java online submissions for Combination Sum II.
Memory Usage: 39.3 MB, less than 49.53% of Java online submissions for Combination Sum II.
Time complexity O(2^n)
Space complexity O(n) Memory Heap size
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
// 1, 2, 2, 6, 7, 10 if we are going to use the duplicate number, then always start with the first
List<List<Integer>> result = new ArrayList<>();
helper(0, candidates, target, new ArrayList<>(), result);
return result;
}
private void helper(int index, int[] candidates, int target, List<Integer> path, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(path));
return;
}
if (index == candidates.length) {
return;
}
for (int i = index; i < candidates.length; i++) {
if (candidates[i] > target) {
break;
}
if (i != index && candidates[i] == candidates[i - 1]) {
continue;
}
path.add(candidates[i]);
helper(i + 1, candidates, target - candidates[i], path, result);
path.remove(path.size() - 1);
}
}
}
三刷
Time Complexity O(2^n) -> generate all subsets
Space Complexity Heap Size -> Tree Height -> O(n)
index == start
98.44 %
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0 || target <= 0) return result;
Arrays.sort(candidates);
helper(0, candidates, target, new ArrayList<>(), result);
return result;
}
// Each layer we subtract a number from remaining target value
// When we see duplicate value, we make sure always get the 1st element at that layer to avoid duplication
private void helper(int start, int[] candidates, int target, List<Integer> path, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int index = start; index < candidates.length && candidates[index] <= target; index++) {
if (index == start || candidates[index] != candidates[index - 1]) {
path.add(candidates[index]);
helper(index + 1, candidates, target - candidates[index], path, result);
path.remove(path.size() - 1);
}
}
}
}
Note:
The variable"i" means represents that we are choosing the ith number in the current layer.
If "i" does not equal to the startIndex of the current layer, we can know that we have skipped the previous number. In this situation, if the current number equals to its previous number, we can know that we are choosing the second number between the 2 same ones, which is not satisfying our requirement. So 1st we'll check (index != startIndex), 2nd we'll check (nums[i] == nums[i - 1]). If both of them are true, we'll need to do "continue" to skip the current i.
二刷
这道题是39的follow up 第五遍了还是index有问题。。。我还能说啥。。。
84.95 %
/*
No one number can be choose twice
sort first
if there's equal numbers e.g. 1 2 2 3
we want to make 1 + 2 + 2 eligible and avoid 1 + 2(1) and 1 + 2(2)
so at the same layer, we always choose the 1st number of the equal ones
*/
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0 || target <= 0) return result;
Arrays.sort(candidates);
dfs(candidates, target, 0, new ArrayList<Integer>(), result);
return result;
}
private void dfs(int[] candidates, int target, int startIndex, List<Integer> path, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<Integer>(path));
return;
}
int curr = 0;
for (int i = startIndex; i < candidates.length; i++) {
curr = candidates[i];
if (curr > target) break;
if (i != startIndex && curr == candidates[i - 1]) continue;
path.add(curr);
dfs(candidates, target - curr, i + 1, path, result);
path.remove(path.size() - 1);
}
}
}
一刷
78.25%public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (candidates == null || candidates.length == 0 || target <= 0) return result;
Arrays.sort(candidates);
helper(candidates, target, 0, new ArrayList<Integer>(), result);
return result;
}
public void helper(int[] candidates, int target, int startIndex, List<Integer> path, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<Integer>(path));
return;
}
for (int index = startIndex; index < candidates.length; index++) {
if (candidates[index] > target) return;
if (index != startIndex && candidates[index] == candidates[index - 1]) continue;
path.add(candidates[index]);
helper(candidates, target - candidates[index], index + 1, path, result);
path.remove(path.size() - 1);
}
}
}
No comments:
Post a Comment