NC50243 小木棍

对于一个长度为num的木段，判断这些被切割之后的小木段能否组成这个长度。我们要枚举每个小木段的长度，每次选当前最长的那个来判断能否组成。选择之后就用num减去这个小木段的长度，继续下一次遍历，如果在下一次遍历中，当前的小木段的长度要比剩余的木段长度要大那么就不选择这个小木段，反之则选择，如果num=0的话，就说明已经组成了一个木段，我们再接着判断剩下的小木段能够组成这个长度的木段。直到小木段数目为0且num为0就说明所有小木段都可以组成这个长度的木段。

剪枝优化：
1.如果当前的小木段在木段的最前面，就说明这个长度不能组成，返回false
2.如果当前的小木段在木段的最后面，也说明这个长度不能组成，返回false
3.n是一个正整数，所以大棍的长度一定是总长度的因子。即枚举答案的时候，若当前枚举出的数值不能被总长度整除，说明这不是一个可能的答案
4.当前长度的小棍试探过后，与这一根相同长度的棍子就不用再试了。

#include <iostream>
#include <algorithm>
using namespace std;
int n;
const int maxn = 66;
int arr[maxn];
bool visit[maxn];
bool cmp(int a, int b) {
    return a > b;
}
bool dfs(int num, int len, int rest,int index ) {
    if (rest == 0 && num == 0)return true;
    if (rest == 0){
        rest = len;
        index=1;
    }
    for (int i = index; i <= n; i++) {
        if (visit[i])continue;
        if (arr[i] > rest)continue;
        visit[i] = true;
        if (dfs(num - 1, len, rest - arr[i],i))return true;
        visit[i] = false;
        if (arr[i] == rest || len == rest)break;
        while (arr[i] == arr[i + 1])i++;
    }
    return false;
}
int main()
{
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }
    sort(arr + 1, arr + n + 1, cmp);
    for (int i = arr[1]; i <= sum; i++) {
        if (sum % i != 0)continue;
        if (dfs(n, i,i,1)) {
            cout << i;
            break;
        }
    }
}