f***s
发帖数: 112 | 1 print all unique solution to split number n, given choice of 1 3 5 10
for example if n is 4
{1, 1, 1, 1}
{1, 3} | k*******q
发帖数: 5493 | 2 动归做的吧
【在 f***s 的大作中提到】
: print all unique solution to split number n, given choice of 1 3 5 10
: for example if n is 4
: {1, 1, 1, 1}
: {1, 3}
| r*******k
发帖数: 1423 | 3 f[N]初始化成0
从f[1]=1开始扫描
依次添可以加的数字
f[1+1],f[1+3],f[1+5],f[1+10]
都存在了一种组合，就是先凑1块f[1]，在加上已知的1，3，5，10
因此
f[2] += f[1]
f[4] += f[1]
...
依次类推
不过好像这么做是排列，不是组合。。。
【在 f***s 的大作中提到】
: print all unique solution to split number n, given choice of 1 3 5 10
: for example if n is 4
: {1, 1, 1, 1}
: {1, 3}
| M**a
发帖数: 848 | 4 dfs吧。
这不就是combination sum么、。 | w*****d
发帖数: 105 | | j**********3
发帖数: 3211 | | a***n
发帖数: 623 | 7 和背包问题没关系吧－>这里有没涉及到背包物品价值的最优化问题。
另上面那个伪码解释完全没看懂，面试官估计也不会懂。
看成一颗4叉树，从左到右分别为1、3、5、10，根到每个叶子节点路径和为target，然
后递归或迭代DFS打印每条路径。 | a***n
发帖数: 623 | 8 // https://oj.leetcode.com/problems/combination-sum/ Accepted.
class Solution {
public:
vector > combinationSum(vector &candidates, int target)
{
vector result;
sort(candidates.begin(), candidates.end());
combinationSum(0, candidates, target, result);
return results_;
}
void combinationSum(int curr, vector &candidates, int target,
vector& result) {
for (int i = curr; i < candidates.size(); ++i) {
if (target < candidates[i]) break;
if (target == candidates[i]) {
result.push_back(target);
results_.push_back(result);
result.pop_back();
break;
}
result.push_back(candidates[i]);
combinationSum(i, candidates, target - candidates[i], result);
result.pop_back();
}
}
vector > results_;
}; | f***s
发帖数: 112 | 9 面试官最后接受了我的解法，我用的是backtracking + 剪支去重复
combination sum
公司第一个字母是D | r*******k
发帖数: 1423 | 10 这样做，不还是一个排列，而不是组合么？
比如11
在你这颗树里面
1+10
10+1
肯定都有，
最后输出的时候，又要费劲去重
【在 a***n 的大作中提到】
: 和背包问题没关系吧－>这里有没涉及到背包物品价值的最优化问题。
: 另上面那个伪码解释完全没看懂，面试官估计也不会懂。
: 看成一颗4叉树，从左到右分别为1、3、5、10，根到每个叶子节点路径和为target，然
: 后递归或迭代DFS打印每条路径。
| | | U***A
发帖数: 849 | 11 这个可以吗？最后一个start是从v中开始查找的位置，这就避免了重复。
vector > addToN(vector& v, int n, int start)
{
int size = (int)v.size();
vector > vv;
if(n < v[0] || n > v[size-1])
{
return vv;
}
for(int i=start; i
{
if(v[i] > n)
{
break;
}
if(v[i] == n)
{
vector v1;
v1.push_back(v[i]);
vv.push_back(v1);
}
else
{
vector > vv1 = addToN(v, n-v[i],i);
for(int j =0; j
{
vector v1;
v1.push_back(v[i]);
v1.insert(v1.begin()+1, vv1[j].begin(), vv1[j].end());
vv.push_back(v1);
}
}
}
return vv;
} | f***s
发帖数: 112 | | b********r
发帖数: 620 | 13 i am always wondering this kind of recursion can pass large number. have you
tried very large number such as 1000+ and see how long that runs?
target)
【在 a***n 的大作中提到】
: // https://oj.leetcode.com/problems/combination-sum/ Accepted.
: class Solution {
: public:
: vector > combinationSum(vector &candidates, int target)
: {
: vector result;
: sort(candidates.begin(), candidates.end());
: combinationSum(0, candidates, target, result);
: return results_;
: }
| y**********a
发帖数: 824 | 14
你这样做，会不会重复计算。
譬如 4=1+3, 4=3+1。
换而言之：
f[4]+=f[1]+3
f[4]+=f[3]+1
【在 r*******k 的大作中提到】
: f[N]初始化成0
: 从f[1]=1开始扫描
: 依次添可以加的数字
: f[1+1],f[1+3],f[1+5],f[1+10]
: 都存在了一种组合，就是先凑1块f[1]，在加上已知的1，3，5，10
: 因此
: f[2] += f[1]
: f[4] += f[1]
: ...
: 依次类推
| y**********a
发帖数: 824 | 15 int combinatorialSum(int[]A,int n) {
int[]rel=new int[1];
dfs(A, new int[A.length], 0, n, rel);
return rel[0];
}
void dfs(int[]A, int[]c, int i, int n, int[]rel) {
if (n==0) {++rel[0];return;}
if (i>=A.length) return;
for (int j=0;n-j*A[i]>=0;++j) {
c[i]+=j;
dfs(A, c, i+1, n-j*A[i], rel);
c[i]-=j;
}
} |
|
