Backtracking

PHOTO EMBED

Thu Aug 18 2022 08:08:24 GMT+0000 (Coordinated Universal Time)

Saved by @Aly #c++ #data_types 

//general approach Template
void Backtrack(int start)
{
    //Base case 

// loop for all possible values
{
    //include the current element at this position if possible in the ans 
	//More generally, make a choice 

    Backtrack(start+1) 

    //backtrack by removing current element 
}
                            ------------------------------------------------

//Generate all subsets (non dublicated)
int n;
void GenerateSubs(vector<int> &a, int s, vector<int> &subset, vector<vector<int>> &ans) {
    for (int i = s; i < n; i++) {
        subset.push_back(a[i]); //include element at ith position
        GenerateSubs(a, i + 1, subset, ans); //generate all subsets including ith element
        subset.pop_back(); //backtrack
    }
    ans.push_back(subset);
}

vector<vector<int>> subsets(vector<int> &a) {
    vector<vector<int>> ans;
    vector<int> subset;
    n = a.size();

    GenerateSubs(a, 0, subset, ans);
    return ans;
}

int main() {
    fast;
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> ans(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    ans = subsets(a);
    for (vector<int> i: ans) {
        for (int j: i) {
            cout << j;
        }
        cout << '\n';
    }
}
// i/p :
  //3
  //1,2,3
// o/p : 
                              ------------------------------------------------

//Generate all subsets (dublicated)
int n;
void GenerateSubs(vector<int>&a,int s,vector<int>&subset,vector<vector<int>>&ans)
{
    for(int i=s;i<n;i++)
    {
        if(i==s||a[i]!=a[i-1])
        {
            subset.push_back(a[i]); //include element at ith position
            GenerateSubs(a,i+1,subset,ans); //generate all subsets including ith element
            subset.pop_back(); //backtrack
        }
    }
    ans.push_back(subset);
}
vector<vector<int>> subsetsWithDup(vector<int> &a) {
    vector<vector<int>> ans;
    vector<int> subset;
    n = a.size();

    sort(a.begin(), a.end()); //sort the elements so that we can keep track of duplicates
    GenerateSubs(a, 0, subset, ans);
    return ans;
}

int main() {
    fast;
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
    freopen("Error.txt", "w", stderr);
#endif
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> ans(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    ans = subsetsWithDup(a);
    for (vector<int> i: ans) {
        for (int j: i) {
            cout << j;
        }
        cout << '\n';
    }
}
// i/p :
  //4
  //1 2 3 2
/* o/p :
1223
122
123
12
13
1
223
22
23
2
3
  */
                              ------------------------------------------------
                              ------------------------------------------------

//---------------------------------------Examples--------------------------------------------------
//Generate all subset instead '?'
string s;
string o;

void solve(int i) {
    //base case
    if (i == s.length()) {
        for (int j = 0; j < s.length(); ++j) {
            cout << o[j];
        }
        cout << '\n';
        return;
    }
    if (s[i] != '?') {
        o[i] = s[i];
        solve(i + 1);
    } else {
        for (int j = 'a'; j <= 'z'; ++j) {
            o[i] = j;
            solve(i + 1);
        }
    }
}


int main() {
    cin >> s;
    solve(0);
}
---------------------------------------------------------------------------------------------------
//Generating Permutations Using next_permutation

int n;
int const N = 11;
bool taken[N];
int stk[N];

void prm(int i) {
    //base case
    if (i == n) {
        for (int j = 0; j < n; ++j) {
            cout << stk[j] << ' ';
        }
        cout << el;
        return;
    }
    for (int j = 1; j <= n; ++j) {
        if (!taken[j]) {
            taken[j] = true;
            stk[i] = j;
            prm(i + 1);
            taken[j] = false;
        }
    }
}


int main() {

    fast;
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
    freopen("Error.txt", "w", stderr);
#endif
    cin >> n;
    prm(0);
}
---------------------------------------------------------------------------------------------------
//
content_copyCOPY