algorithm - 确定一个数字的可能组合的数量以获得指定的结果

Question

我遇到了这个问题:

给定一个整数，仅使用 2、3、7 来确定可能组合的数量，其总和将给出整数。

例如:

4 - 2  {(2,2)}
9 - 3  {(2, 7), (2, 2, 2, 3), (3, 3, 3)}

一种方法是迭代3个循环，然后判断总和是否可以达到。这是代码:

for( i=0; i<=num/2; i++){
    for( j=0; j<=num/3; j++){
         for( k=0; k<=num/7; k++){
            if(i*2+j*3+k*7 == num) 
                 count++;
}

这里 count 将有可能的集合数。但这是非常低效的，需要 O(n3) 的时间。我想知道是否有任何其他有效的方法来计算不同集合的数量。

Answer 1

这可以在 O(n^2) 中解决。

只是避免你的最后一个循环。

for( i=0; i<=num/2; i++){
    for( j=0; j<=num/3; j++){
        k = num - i*2 - j*3;
        if(k%7==0)
                 count++;
    }
}