Hi everyone, I am solving a problem where i need to find the min number of coins such that total sum is equal to sum. My given solution is not working if i use long long ans = INT_MAX; and it is taking too long but it is working long long ans = 10000000; for the given testcase. Can somebody help me to find the issue why it is not working with INT_MAX? For example, if the coins are {1,5,7} and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins. I would request you to copy paste in your ide and run with below testcase because ans= INT_MAX making code stuck in loop.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define f(i, p, q) for (int i = p; i < q; i++)

ll dp[1000003];

long long solve(int n, int sum, int *ar) {
    if (sum == 0) return 0;
    if (dp[sum] != INT_MAX) return dp[sum];

    // long long ans = 10000000;
     long long ans = INT_MAX;

    for (int i = 0; i < n; i++) {
        if (sum - ar[i] >= 0) {
            ans = min(ans, 1 + solve(n, sum - ar[i], ar));
        }
    }

    dp[sum] = ans;
    return ans;
}
int main()
{
    int n,m;
    cin >> n>>m;
    int ar[n];
    f(i,0,n)cin>>ar[i];
    f(i,0,1000003)dp[i]= INT_MAX;
    int a =solve(n,m, ar);
    cout<< ((a== 10000000)? -1 : a);
}

100 1000000 649304 85832 159093 841262 930486 225095 306941 914339 469211 156923 460959 236712 440066 842678 379057 615269 321673 694036 378785 792217 78290 15844 644234 752342 102458 30237 191522 388758 697655 113684 20857 639493 641307 527161 977787 505822 196847 735190 169901 417528 342499 102964 907594 780802 577476 162325 790726 579970 148134 144070 624899 392951 594195 813112 534969 856431 25058 630213 641105 636550 762730 873997 275210 717753 243026 915205 52253 613173 751823 647785 928932 305278 858885 496267 717378 426281 245531 139541 942976 912031 550043 194533 504278 552822 805186 950257 673230 484067 790808 762595 590958 799224 711398 599947 858840 212470 820350 710862 546121 159727

Hi, My below code return a output and not passing the testcase even it satisfy the condition. Can somebody help me why it is failing? Problem link : https://cses.fi/problemset/task/2205/ For input : 3

My output: 000 100 110 010 101 001 011 111 CSES OUTPUT: 000 001 011 010 110 111 101 100 Code:

#include <bits/stdc++.h>
#define ll long long int
#define f(i, p, q) for (int i = p; i < q; i++)
using namespace std;
vector<string>v;
void solve(int n,string s){
    if(s.length()>=n){
        v.push_back(s);
        return;
    }
    solve(n,s+'0');
    solve(n,s+'1');
}
int countOne(string s){
    int count=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='1')count++;
    }
    return count;
}
int main()
{
   
    int n;
    cin>>n;

    solve(n,"");
    map<int,vector<string>>mp;
    int ans=0;
    for(int i=0;i<v.size();i++){
        mp[countOne(v[i])].push_back(v[i]);
    }
    int l=0;
    bool x= false;
    for(ll i=0;i<=pow(2,n);i++){
        if(mp[l-1].size()>0 && x){
            string g =mp[l-1][mp[l-1].size()-1];
            cout<<g<<"\n";
            mp[l-1].pop_back();
            x=false;
        }else if(mp[l].size()>0 && !x){
            string g =mp[l][mp[l].size()-1];
            cout<<g<<"\n";
            mp[l].pop_back();
            x=true;      
        }
        if(mp[l-1].size()==0){   
           l++;
           x= true;
        }
    }  
}