a981: 求和問題

2019-08-14

內容

給你 N 個正整數, 試求哪幾個之和剛好為 M, 印出所有合條件的解, 如有多組解, 請按由小到大的順序印出(格式可參考樣例輸出)

輸入

n m (1<=n<=30, 1<=m<=100000000)

n 個正整數, 全部以空格分開

10 100
10 20 40 30 50 80 60 70 5 15

輸出

其和剛好等於 m 的數, 如果有多組解則按由小到大全部印出, 如果無解則印出-1

5 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60

解題思路

由於要由小至大輸出，所以先把數字按順序排好，接下來窮舉全部的可能，如果窮舉過程中被窮舉到的值相加等於目標值則印出答案。

因為窮舉到的值相加超過目標值之後不可能再出現”窮舉到的值總和 = 目標值”的情況，所以可以把它剪枝掉。

又因為窮舉的陣列已經被排序過了，下一個窮舉值必 ≥ 當前窮舉值，所以當窮舉到的值總和 + 當前的窮舉值 > 目標值時，接下來也都不可能再出現”窮舉到的值總和 = 目標值”，所以當發生這種情況時也可以進行剪枝。

完整程式碼

AC (0.2s, 96KB)

#include <stdio.h>
#include <stdlib.h>

int n, m, next, list[50], output[50];
char noAns;

int cmp(const int* lhs, const int* rhs)
{
    return *lhs - *rhs;
}

void dfs(int sum, int start, int depth)
{
    for (int i = start; i < n; i++)
    {
        next = sum + list[i];
        if (next >= m)
        {
            if (next == m)
            {
                for (int j = 0; j < depth; j++)
                    printf("%d ", output[j]);
                printf("%d\n", list[i]);
                noAns = 0;
            }
            if (list[i] < list[i + 1])
                return;
        }
        output[depth] = list[i];
        if (next + list[i] <= m)
            dfs(next, i + 1, depth + 1);
    }
}

int main()
{
    while (scanf(" %d %d", &n, &m) == 2)
    {
        noAns = 1;
        for (int i = 0; i < n; i++)
            scanf(" %d", &list[i]);
        qsort(list, n, sizeof(int), cmp);
        dfs(0, 0, 0);
        if (noAns)
            puts("-1");
    }
    return 0;
}