f*********m
发帖数: 726 | 1 题目如下，求code。非常感谢。
Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find
all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … ,ak) must be in non-descending
order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6] | T****U
发帖数: 3344 | 2 跟3sum一样，搜leetcode 3sum
【在 f*********m 的大作中提到】
: 题目如下，求code。非常感谢。
: Combination Sum II
: Given a collection of candidate numbers (C) and a target number (T), find
: all unique combinations in C where the candidate numbers sums to T.
: Each number in C may only be used once in the combination.
: Note:
: All numbers (including target) will be positive integers.
: Elements in a combination (a1, a2, … ,ak) must be in non-descending
: order. (ie, a1 ≤ a2 ≤ … ≤ ak).
: The solution set must not contain duplicate combinations.
| f*********m
发帖数: 726 | 3 3sum不用递归，O(n^2)复杂度。这个问题估计不是吧？ | r********g
发帖数: 1351 | 4 写了个递归的，复杂度。。应该是C(n,k)吧？指数级的？
class Solution {
public:
vector > combinationSum2(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num);
vector > Results;
vector tmpR;
doFind(num, Results, 0, target, tmpR);
return Results;
}
void doFind(vector &num, vector > &Results, int idx,
int target, vector tmpR) {
if(target == 0) {
Results.push_back(tmpR);
return;
}
if(idx >= num.size() || target < 0) return;
int count = 1;
while(idx < num.size()-1 && num[idx] == num[idx+1]) {
idx++;
count++;
}
vector Tmp(tmpR);
while(target >= 0 && count>=0){
doFind(num, Results, idx+1, target, Tmp);
Tmp.push_back(num[idx]);
target -= num[idx];
count--;
}
}
};
【在 f*********m 的大作中提到】
: 3sum不用递归，O(n^2)复杂度。这个问题估计不是吧？
| f*********m
发帖数: 726 | 5 我也贴一个：
void CombinationSumII(vector & I, int start, vector &O, int sum,
vector > &ret)
{
if(sum == 0)
{
ret.push_back(O);
return;
}
if(start == I.size() || sum < 0)
return;
int prev = -1;
for(int i = start; i < I.size(); i++)
{
if (I[i] != prev)
{
O.push_back(I[i]);
CombinationSumII(I, i+1, O, sum - I[i], ret);
O.pop_back();
prev = I[i];
}
}
}
vector > combinationSum2(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
vector O;
sort(num.begin(), num.end());
CombinationSumII(num, 0, O, target, ret);
return ret;
} | S******1
发帖数: 269 | 6 Basically the same solution with repeatable candidates. Recursion, time
complexity should be O(n!)?
import java.util.*;
public class Solution {
public ArrayList> combinationSum2(int[] num, int
target) {
ArrayList> result= new ArrayList
Integer>> ();
ArrayList item=new ArrayList ();
Arrays.sort(num);
if(num!=null || num.length>0)
combinations(num, target, result, item, 0);
return result;
}
public void combinations(int num[], int target, ArrayList
Integer>> result, ArrayList item, int startIndex){
if(target<0||startIndex>num.length)
return;
if(target==0){
result.add((ArrayList)item.clone());
return;
}
for(int i=startIndex; i
item.add(num[i]);
combinations(num, target-num[i], result,item, i+1);
item.remove(item.size()-1);
while(i+1
i++;
}
}
}
} |
|
