TLE for Spoj BTCK

Question

Hey there I have been working on this question recently but am unable to solve this question using backtracking.

Question : You have to solve the following problem with Backtracking. You're given a sequence of 10 positive integers n1 , n2 , n3 , ... ,n9, n10 and a positive value K.

To solve this problem you need to print a permutation a1 , a2 , a3 , ... ,a10 of the numbers {0,1,2,3,4,5,6,7,8,9} such that a1 * n1 + a2 * n2 + a3 *n3 + ... + a10*n10 ≤ K

Among all the permutations that solve the problem according to the description above, print the lexicographically smallest.

Link to question

My code goes as follows:

#include <algorithm>
#include <iostream>

#define ll long long
#define forn(i,a,b) for(int i = a; i < b; i++)

using namespace std;

ll k;
bool solved = 0; // Tells if we have found a solution or not.
int ans[10];  // Will contain the final sequence of ai s
int arr[10];  // Contains the numbers provided in the question. For this example arr[] = {1,2,3,4,5,6,7,8,9,10}
bool vis[10]={false}; // Denotes if the value ai(see the question) has been used or not

void print();

bool solve(int n, ll sum, int movei)  // n = 10 , movei => which number we have to assign ai to.
{
    if(sum > k) {
            return false;   // Backtrack
    }
    if(movei == n)
    {
        return sum<=k;
    }
    forn(i,movei,n)
    {
        forn(j,0,10)
        {
            if(vis[j]) continue;
            ans[i]=j;
            vis[j]=1;
            if(solve(n, sum + arr[i]*j, movei+1)) return true; // If we found a solution return true
            vis[j]=0;
        }
    }
    return false; // We could not find any solution at all.
}

void print()
{
    forn(i,0,10)
    cout << ans[i] << " ";
}

int main()
{
    int t;         // Number of test cases
    //cin >> t;
    t = 1;
    while(t--)
    {
        forn(i,0,10) arr[i] = i+1; //cin >> arr[i];
        cin >> k;
        if(solve(10,0LL,0)) print();
        else cout << -1;
        cout<<endl;
    }
}

Approach :
1) Check for all the paths
2) If you find a solution then that's gonna be the lexicographially smallest order and so return true, meaning solution is found else
3) Continue to look for the solution.
4) If you cannot find a solution in any path then return false, meaning solution cannot be found in which case I print -1.

How can I solve this question. I have been really working hard on this but can not think anything else.

Answer 1

Thank you @juvian and @PaulMcKenzie for your replies. Code is as follows,

#include <algorithm>
#include <iostream>

using namespace std;

void print(int a[], int n)
{
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
}

int main()
{
    int test;
    cin >> test;
    int n[10], a[10], k;
    while(test--)
    {
        for(int i = 0; i < 10; i++)
        cin >> n[i];
        cin >> k;

        bool solved = false;

        for(int i = 0; i < 10; i++) a[i] = i;

        do
        {
            int k1 = 0;
            for(int i = 0; i < 10; i++)
            {
                k1 += n[i]*a[i];
            }
            if(k1 <= k)
            {
                solved = true;
                print(a, 10);
                break;
            }
        }while(next_permutation(a, a+10));

        if(!solved) cout << -1;
        cout << endl;
    }
    return 0;
}