m*******1
发帖数: 77 | 1 这个题最后为了避免重复，我用了一个set结构，有什么更好的方法来避免重复吗？ | p*****2
发帖数: 21240 | | m*******1
发帖数: 77 | 3 那循环已有的查查看有无重复？
【在 p*****2 的大作中提到】
: 这题可能要求不可以用extra space。
| c********r
发帖数: 286 | 4 请教二爷，不用extra space如何避免呢？
【在 p*****2 的大作中提到】
: 这题可能要求不可以用extra space。
| p*****2
发帖数: 21240 | 5
要不要我现写一个呀。
【在 c********r 的大作中提到】
: 请教二爷，不用extra space如何避免呢？
| e******o
发帖数: 757 | 6 I think it is similar to combination sum I.
sort the array first.
in combination sum I, you can use a number unlimited times.
but in II, if a number appears n times, then you can use it at most n times
. | p*****2
发帖数: 21240 | 7
times
确实similar。代码非常类似。
【在 e******o 的大作中提到】
: I think it is similar to combination sum I.
: sort the array first.
: in combination sum I, you can use a number unlimited times.
: but in II, if a number appears n times, then you can use it at most n times
: .
| s*********s
发帖数: 140 | 8 同问如何不用extra hashset避免duplicate。 | r*****e
发帖数: 792 | 9 my code which passed online judge:
void solveSum2(vector &num, int tgt, vector > &res, int sum
, int idx, vector &index) {
if (sum>tgt) return ;
if (sum==tgt) {
vector one;
for (size_t k=1; k
one.push_back(num[index[k]]);
res.push_back(one);
return;
}
for (size_t i=index[idx]; i
if (sum>0 && i==(size_t)index[idx]) continue;//avoid adding the same
beginning index one more time
index.push_back(i);
solveSum2(num, tgt, res, sum+num[i], idx+1, index);
int back=num[index.back()];
while (i+1
index.pop_back();
}
}
vector > combSum2(vector &num, int tgt) {
vector > res;
vector index;
index.push_back(0);//need this!
sort(num.begin(), num.end());
solveSum2(num, tgt, res, 0, 0, index);
return res;
}
【在 m*******1 的大作中提到】
: 这个题最后为了避免重复，我用了一个set结构，有什么更好的方法来避免重复吗？
| m*******1
发帖数: 77 | 10 这个题最后为了避免重复，我用了一个set结构，有什么更好的方法来避免重复吗？ | | | p*****2
发帖数: 21240 | | m*******1
发帖数: 77 | 12 那循环已有的查查看有无重复？
【在 p*****2 的大作中提到】
: 这题可能要求不可以用extra space。
| c********r
发帖数: 286 | 13 请教二爷，不用extra space如何避免呢？
【在 p*****2 的大作中提到】
: 这题可能要求不可以用extra space。
| p*****2
发帖数: 21240 | 14
要不要我现写一个呀。
【在 c********r 的大作中提到】
: 请教二爷，不用extra space如何避免呢？
| e******o
发帖数: 757 | 15 I think it is similar to combination sum I.
sort the array first.
in combination sum I, you can use a number unlimited times.
but in II, if a number appears n times, then you can use it at most n times
. | p*****2
发帖数: 21240 | 16
times
确实similar。代码非常类似。
【在 e******o 的大作中提到】
: I think it is similar to combination sum I.
: sort the array first.
: in combination sum I, you can use a number unlimited times.
: but in II, if a number appears n times, then you can use it at most n times
: .
| s*********s
发帖数: 140 | 17 同问如何不用extra hashset避免duplicate。 | r*****e
发帖数: 792 | 18 my code which passed online judge:
void solveSum2(vector &num, int tgt, vector > &res, int sum
, int idx, vector &index) {
if (sum>tgt) return ;
if (sum==tgt) {
vector one;
for (size_t k=1; k
one.push_back(num[index[k]]);
res.push_back(one);
return;
}
for (size_t i=index[idx]; i
if (sum>0 && i==(size_t)index[idx]) continue;//avoid adding the same
beginning index one more time
index.push_back(i);
solveSum2(num, tgt, res, sum+num[i], idx+1, index);
int back=num[index.back()];
while (i+1
index.pop_back();
}
}
vector > combSum2(vector &num, int tgt) {
vector > res;
vector index;
index.push_back(0);//need this!
sort(num.begin(), num.end());
solveSum2(num, tgt, res, 0, 0, index);
return res;
}
【在 m*******1 的大作中提到】
: 这个题最后为了避免重复，我用了一个set结构，有什么更好的方法来避免重复吗？
| t*******e
发帖数: 274 | 19 有没有java solution么？下面的代码是combination sum的，怎么在这个基础上改呢？
public class Solution {
public ArrayList> combinationSum(int[] candidates,
int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> results = new ArrayList
Integer>>();
Arrays.sort(candidates);
addUp(candidates, 0, target, new ArrayList(), results);
return results;
}
private void addUp(int[] candidates, int start, int target, ArrayList<
Integer> path, ArrayList> results) {
if (start < 0 || start >= candidates.length || target < 0) return;
if (target == 0) {
ArrayList res = new ArrayList(path);
results.add(res);
} else {
for (int i=start; i
if (candidates[i] > target) continue; // we cannot break
since data may not be sorted
path.add(candidates[i]);
addUp(candidates, i, target - candidates[i], path, results);
path.remove(path.size() - 1);
}
}
}
} |
|
