Let be the number of candidates, be the target value, and be the minimal value among the candidates.
Time Complexity:
As we illustrated before, the execution of the backtracking is unfolded as a DFS traversal in a n-ary tree. The total number of steps during the backtracking would be the number of nodes in the tree.
At each node, it takes a constant time to process, except the leaf nodes which could take a linear time to make a copy of combination. So we can say that the time complexity is linear to the number of nodes of the execution tree.
Here we provide a loose upper bound on the number of nodes.
First of all, the fan-out of each node would be bounded to , i.e. the total number of candidates.
The maximal depth of the tree, would be , where we keep on adding the smallest element to the combination.
As we know, the maximal number of nodes in N-ary tree of height would be .
Note that, the actual number of nodes in the execution tree would be much smaller than the upper bound, since the fan-out of the nodes are decreasing level by level.
Space Complexity:
We implement the algorithm in recursion, which consumes some additional memory in the function call stack.
The number of recursive calls can pile up to , where we keep on adding the smallest element to the combination. As a result, the space overhead of the recursion is .
In addition, we keep a combination of numbers during the execution, which requires at most space as well.
To sum up, the total space complexity of the algorithm would be .
Note that, we did not take into the account the space used to hold the final results for the space complexity.
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
dfs(candidates, candidates.length - 1, new ArrayList<>(), result, target);
return result;
}
private void dfs(int[] candidates, int index, List<Integer> path, List<List<Integer>> result, int target) {
if (target <= 0) {
if (target == 0) {
result.add(new ArrayList<>(path));
}
return;
}
for (int i = index; i >= 0; i--) {
path.add(candidates[i]);
dfs(candidates, i, path, result, target - candidates[i]);
path.remove(path.size() - 1);
}
}
}
三刷
写了这么多遍还是在index上有问题啊。。。疯了
跟二刷写的一样
一刷不懂为啥要去重，可能原来没有duplicates这个条件
94.37 %
//for every layer, choose a number from candidates and subtract it from the target
//prunning-try to add from smaller to larger
//once the number is larger than the target, we can break the current layer(positive integers)
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0 || target <= 0) return result;
//O(nlogn)
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];
//Ensures that {target} will never be less than 0
if (curr > target) break;
path.add(curr);
//can add the same numbers
dfs(candidates, target - curr, i, path, result);
path.remove(path.size() - 1);
}
}
}
一刷
It is worth mentioning that the removeDuplicates method uses in place duplication remove algorithm.
public class Solution {
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// write your code here
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return result;
}
int[] nums = removeDuplicates(candidates);
dfs(nums, target, 0, new ArrayList<Integer>(), result);
return result;
}
//call dfs recursively
//add path to result list
public void dfs(int[] nums, int target, int startIndex,
List<Integer> path, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<Integer>(path));
return;
}
for (int i = startIndex; i < nums.length; i++) {
if (nums[i] > target) return;
path.add(nums[i]);
dfs(nums, target - nums[i], i, path, result);
path.remove(path.size() - 1);
}
}
//1.sort
//2.remove duplicates
public int[] removeDuplicates(int[] candidates) {
Arrays.sort(candidates);
int index = 0;
for (int i = 0; i < candidates.length; i++) {
if (candidates[i] != candidates[index]) {
candidates[++index] = candidates[i];
}
}
int[] nums = new int[index + 1];
for (int j = 0; j < nums.length; j++) {
nums[j] = candidates[j];
}
return nums;
}
}
二刷
73.69%
public class Solution {
public List<List<Integer>> combinationSum(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;
path.add(candidates[index]);
helper(candidates, target - candidates[index], index, path, result);
path.remove(path.size() - 1);
}
}
}
No comments:
Post a Comment