@xysrGeeemm
list.remove(int index).
It means remove the last element of a list.
The index of last element in a list is (list.size() -1). : )
@xysrGeeemm
list.remove(int index).
It means remove the last element of a list.
The index of last element in a list is (list.size() -1). : )
In fact, the array given does not need to be sorted.
Use a array to record every element's times used for the combination, if times==0, do not add it to a result.
Every time we try to reduce 1 element from the last. When target < 0 or lengh ==0 the recursive can be stopped.
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if (candidates == null || candidates.length == 0 || target <= 0)
return res;
// Every number has 0 times initially.
int[] times = new int[candidates.length];
combinationSum(res, candidates, candidates.length, times, target);
return res;
}
private void combinationSum(List<List<Integer>> res, int[] candidates,
int length, int[] times, int target) {
// Get the proper combination.
if (target == 0) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < candidates.length; i++) {
int n = times[i];
while (n-- > 0)
list.add(candidates[i]);
}
res.add(list);
return ;
}
// No numbers to use, just stop the recursive.
if (length == 0 || target < 0) return ;
// Max times for the current number.
int curIndex = length - 1;
int maxTimes = target / candidates[curIndex];
for (int i = maxTimes; i >= 0; i--) {
times[curIndex] = i;
combinationSum(res, candidates, curIndex, times, target - i * candidates[curIndex]);
}
}
@monaziyi A occasion case can not reflect the truth. Even a different running environment can cause some error. What's more, a very-long string can show the great improvement with an O(logN) method.
@cdai A short String case may cause KMP is slower than brute force since you made a next[] before iteration.
A longer String and more repeated long substring can show the great improvement by KMP. ：）
@Ray_Jiang Arrays.sort() takes O(N * logN) while the process takes O(N^2), so O(N * logN) + O(N^2) = O(N^2)
@fsr0023120 hi bro, I tried with "prefix" a StringBuilder type, and the answer is not correct. Because String is a const while StringBuilder causes a reference-pass during the recursive. So if input "abc" it turns out "a", "ab" and "abc".
@shpolsky
Two points to improve:
1.Since the array is sorted, if nums[i] > 0, we should get out of the loop because it is impossible to find another two numbers to get sum of 0;
2.Bi-directional search should pass the duplicated numbers to reduce iteration.
Anyway, thx for share~ : ) 👻