POJ #1011 - Sticks

This is really classic searching problem to solve. The key is pruning.

//    1011


#include <stdio.h>
#include <stdlib.h>
#include <algorithm> 
using namespace std;

#define MAX_STICK 64

bool cmp (int i,int j) { return (i > j); }

bool dfs(int *sticks, bool *visited, int currLen, int tgtLen, int currInx, int usedCnt, int n)
{
    if(usedCnt == n) return true;

    int skipLen = -1;
    for(int i = currInx; i < n; i ++ )
    {
        if(visited[i] || sticks[i] == skipLen) continue;    // Pruning 3: if that len needs to be skipped
        
        visited[i] = true;

        int currCmb = currLen + sticks[i];
        if(currCmb < tgtLen)
        {
            if(dfs(sticks, visited, currCmb, tgtLen, i, usedCnt + 1, n))
                return true;
            else
                skipLen = sticks[i]; 
        }
        else if(currCmb == tgtLen)
        {
            if(dfs(sticks, visited, 0, tgtLen, 0, usedCnt + 1, n))
                return true;
            else
                skipLen = sticks[i]; 
        }

        visited[i] = false;    
        
        if(currLen == 0) break;    // Pruning 4: for starting point 0, no matches then NO
                                // * it makes TLE passing as 16MS
    }
    return false;
}

int main()
{
    int n; 
    while (scanf("%d", &n), n != 0)
    {
        int sticks[MAX_STICK] = { 0 };
        bool visited[MAX_STICK]    = { false };

        //    Input
        int sum = 0;
        for(int i = 0; i < n; i ++) 
        {
            scanf("%d", sticks + i);
            sum += sticks[i];
        }

        //    Sort descending
        sort (sticks, sticks + n, cmp);

        //    Searching by pruning
        bool bFound = false;
        for(int l = sticks[0]; l <= sum - l; l ++)    //    Pruning 1
        {
            if( (sum % l == 0) && dfs(sticks, visited, 0, l, 0, 0, n))    // Pruning 2
            {
                bFound = true;
                printf("%d\n", l);
                break;
            }
        }
        if(!bFound)    printf("%d\n", sum);        
    }
    return 0;
}      

View Code