小木棍C++解法

解题思路:回溯回到底

注意事项:无

参考代码:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> sticks;

vector<bool> used;

int total_len;

int target;

int cnt;

// 回溯函数

bool backtrack(int cur_len, int finished) {

    if (finished == cnt) return true;

    for (int i = 0; i < sticks.size(); ++i) {

        if (used[i] || (i > 0 && !used[i - 1] && sticks[i] == sticks[i - 1]))

            continue;

        if (cur_len + sticks[i] > target)

            continue;

        used[i] = true;

        if (cur_len + sticks[i] == target) {

            if (backtrack(0, finished + 1)) return true;

        } else {

            if (backtrack(cur_len + sticks[i], finished)) return true;

        }

        used[i] = false;

        if (cur_len == 0) return false;

    }

    return false;

}

int main() {

    int n;

    cin >> n;

    sticks.resize(n);

    total_len = 0;

    for (int i = 0; i < n; ++i) {

        cin >> sticks[i];

        total_len += sticks[i];

    }

    sort(sticks.begin(), sticks.end(), greater<int>()); // 降序排序

    for (target = sticks[0]; target <= total_len; ++target) {

        if (total_len % target != 0)

            continue;

        cnt = total_len / target;

        used.assign(n, false); // 初始化used数组

        if (backtrack(0, 0)) {

            cout << target << endl; // 使用cout输出结果

            return 0;

        }

    }

    return 0;

}