Hey Simes, I had tried this approach too but it gives TLE. Then I eventually solved it by using std::next_permutation(overall complexity (O(length_of_array * 10!) ~ O(10^7))
but I still am not abe to solve this using backtracking, we need a little bit more optimization. Please suggest if you have one. I am posting my code where I have used backtracking
#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(ni) 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;
}
}
Please ignore the variables I have declared as global, I know it is not a good practice to do so. Next time I will declare them as local variables 