Help needed in backtracking problem!

problem statement → Find all combinations of elements satisfying given constraints

help me to find out my logical error!

image

my code

#include<unordered_set>
class Solution{
public:
void findall(int curr, int n, vector<int>&vec, set<vector<int>>&combinations, unordered_set<int> &s){
         
         if(s.size()==n){
              combinations.insert(vec);
              return;
         }
         if(curr>=2*n) return;   
         
         if(vec[curr]!=-1){
             findall(curr+1,n,vec,combinations,s);
         }else{
            for(int i=1;i<=n;i++){
             if(((curr+i+1)<2*n)&&(s.find(i)==s.end())&&curr>=0){
                 vec[curr] = i;
                 vec[curr+i+1] = i;
                 s.insert(i);
                 findall(curr+1,n,vec,combinations,s);
                 s.erase(i);
                 vec[curr] = -1;
                 vec[curr+i+1] = -1;
             } 
           }
         }
    }

	set<vector<int>> findCombinations(int n){
		set<vector<int>> combinations;
		vector<int> vec(2*n,-1);
		unordered_set<int> s;
        findall(0,n,vec,combinations,s);
		return combinations;
	}
};

your if condition on the 16th line is missing one more check.
The position at (curr+i+1) also has to be empty to put a number at that position.
So adding vec[curr+i+1]==-1 check on line 16 will suffice.

1 Like