请教一道面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道面试题

请教一道面试题# JobHunting - 待字闺中

x*x2010-09-21 07:09

1 楼

Given a target number, and a series of candidate numbers, print out all
combinations, so that the sum of candidate numbers equals to the target.
Here order is not important, so don't print the duplicated combination.
e.g. target is 7, candidate is 2,3,6,7
output should be 7; or 3+2+2 (but not print 2+3+2, 2+2+3)
How to write the code to solve it? Thanks!

t*j2010-09-21 07:09

2 楼

sort first，然后dynamic programming，如果找到match的就打印。

【在 x**x 的大作中提到】

: Given a target number, and a series of candidate numbers, print out all
: combinations, so that the sum of candidate numbers equals to the target.
: Here order is not important, so don't print the duplicated combination.
: e.g. target is 7, candidate is 2,3,6,7
: output should be 7; or 3+2+2 (but not print 2+3+2, 2+2+3)
: How to write the code to solve it? Thanks!

p*72010-09-21 07:09

3 楼

这个和coin没区别

m*g2010-09-21 07:09

4 楼

dynamic programming is good

h*62010-09-21 07:09

5 楼

这题相当于今年Codejam Round 3最后一题的第一小问，面试现场能在白板上45分钟写
出来的都是神人。

x*x2010-09-21 07:09

6 楼

是么？你见的题真多。
这是facebook phone interview的题，只有25分钟，要在shared doc里写code.
看上去也不是很难，但是我没有做好。 :(

【在 h**6 的大作中提到】

: 这题相当于今年Codejam Round 3最后一题的第一小问，面试现场能在白板上45分钟写
: 出来的都是神人。

t*a2010-09-21 07:09

7 楼

DP is good but I don't think sorting is necessarily here...
solution(n, set) = union([set[0], solution(n-set[0], set)] , solution(n, set
[1:]))

【在 t*****j 的大作中提到】

: sort first，然后dynamic programming，如果找到match的就打印。

l*e2010-09-21 07:09

8 楼

需要吧
要避免重复的比如5=3+2, 2+3

set

【在 t****a 的大作中提到】

: DP is good but I don't think sorting is necessarily here...
: solution(n, set) = union([set[0], solution(n-set[0], set)] , solution(n, set
: [1:]))

t*j2010-09-21 07:09

9 楼

sorting是为了保证不重复打印。

set

【在 t****a 的大作中提到】

: DP is good but I don't think sorting is necessarily here...
: solution(n, set) = union([set[0], solution(n-set[0], set)] , solution(n, set
: [1:]))

l*e2010-09-21 07:09

10 楼

peng

【在 t*****j 的大作中提到】

: sorting是为了保证不重复打印。
:
: set

x*x2010-09-21 07:09

11 楼

不知道哪位大侠能写一下code, thanks!

【在 t*****j 的大作中提到】

: sorting是为了保证不重复打印。
:
: set

n*h2010-09-21 07:09

12 楼

no sorting needed. see code below.
void f_(int[] array, int sum, int limit, StringBuffer b){
if(sum == 0){
b.print();
return;
}
for(int i=0; iif(array[i] <= limit && sum - array[i] >= 0){
b.append("+" + array[i]);
f_(array, sum - array[i], array[i], b);
b.remove_last();
}
return;
}
void f(int[] array, int sum){
StringBuffer b = new StringBuffer("");
f_(array, sum, sum, b);
}
for the posted problem, we just write:
int a[]={2,3,4,6};
f(a, 7);

K*g2010-09-21 07:09

13 楼

How can you guarantee no repeated combinations?

【在 n******h 的大作中提到】

: no sorting needed. see code below.
: void f_(int[] array, int sum, int limit, StringBuffer b){
: if(sum == 0){
: b.print();
: return;
: }
: for(int i=0; i: if(array[i] <= limit && sum - array[i] >= 0){
: b.append("+" + array[i]);
: f_(array, sum - array[i], array[i], b);

c*s2010-09-21 07:09

14 楼

static void printSum(int[] a, int index, int sum, ArrayList
results) {
if (sum == 0) {
System.out.println(results);
return;
}
for (int i = index; i < a.length; i++) {
if (sum >= a[i]) {
results.add(a[i]);
printSum(a, i, sum - a[i], results);
results.remove(results.size() - 1);
}
}
}
@Test
public void testPrintSum() {
printSum(new int[] { 1, 2, 6, 7, 3 }, 0, 7, new ArrayList());
}
Output:
[1, 1, 1, 1,

i*e2010-09-21 07:09

15 楼

Idea: Use recursion to solve. Recursion is like printing all possible
combination from a list of integers. To avoid duplicate result sets, sort
the candidate array first.
This solution assumes that the candidate array does not have any duplicates.
Remove all duplicates first if the candidate array does have duplicates.
void printSum(int candidates[], int index[], int n) {
for (int i = 1; i <= n; i++)
cout << candidates[index[i]] << " ";
cout << endl;
}
void solve(int target, int sum, int

r*u2010-09-21 07:09

16 楼

试了你的code，把sort comment掉也不会有重复，你试试。

duplicates.

【在 i**********e 的大作中提到】

: Idea: Use recursion to solve. Recursion is like printing all possible
: combination from a list of integers. To avoid duplicate result sets, sort
: the candidate array first.
: This solution assumes that the candidate array does not have any duplicates.
: Remove all duplicates first if the candidate array does have duplicates.
: void printSum(int candidates[], int index[], int n) {
: for (int i = 1; i <= n; i++)
: cout << candidates[index[i]] << " ";
: cout << endl;
: }