dfs

 avatar
user_8384735
c_cpp
3 years ago
2.2 kB
6
Indexable
// 307v3.cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100
using namespace std;

bool isUsed[N], path[N];

int sticks[N],n;
bool backtracking(int idx, int count, int now, int len);
void chak(){
    for (int i = 0; i < n; i++){
        if (path[i]){
            std::cout << sticks[i] << " ";
            path[i] = 0;
        }
    }
    std::cout << endl;
}
int main()
{
    int i;
    while (scanf("%d", &n) && n)
    {
        int all = 0;
        for (i = 0; i < n; i++)
        {
            scanf("%d", &sticks[i]);
            all += sticks[i];
        }

        sort(sticks, sticks + n, [](const int& a, const int& b)->bool{return a > b; });
        fill(isUsed, isUsed + n, false);
        int len;
        for (len = sticks[0]; len <= all; len++)
        {
            for (int i = 0; i < n; i++)
                cout << (isUsed[i] == 0);
            cout << endl;
            if (all%len)
                continue;

            if (backtracking(0, 0, 0, len))
                break;
            
        }

        printf("%d\n", len);
    }

    return 0;
}
bool backtracking(int idx, int count, int now, int len)
{
    if (now == len)
    {
        //chak();
        if (count == n)
            return true;
        now = 0;
    }

    if (!now)
    {
        for (idx = 0; isUsed[idx]; idx++);
        isUsed[idx] = path[idx] = true;
        if (backtracking(idx + 1, count+1, sticks[idx], len))
            return true;
        isUsed[idx] = path[idx] = false;
    }
    else
    {
        for (int i = idx; i < n; i++)
        {
            if (isUsed[i] || (i&&sticks[i] == sticks[i - 1] && !isUsed[i - 1]))
                continue;

            if (now + sticks[i] <= len)
            {
                isUsed[i] = path[i] = true;
                if (backtracking(i + 1, count+1, now + sticks[i], len))
                    return true;
                isUsed[i] = path[i] = false;
                
                if (now + sticks[i] == len)
                    return false;
            }
        }
    }

    return false;
}
Editor is loading...