Backtracking Fundamentals

Backtracking builds answers one decision at a time: choose, explore recursively, then undo the choice. It is useful when solutions are small structured objects such as permutations, subsets or combinations. A pruning rule skips a branch only when it cannot produce a required answer. Our three clearly separated functions enumerate objects from {1,…,n}; advanced constraint-search heuristics are outside this introductory lesson.

Prerequisites: Recursion Fundamentals; vectors; Boolean conditions.

Build the idea

1. 1. Keep the partial solution valid

   path stores choices already made. In permutations, used[x] prevents choosing the same number twice. When path reaches length n, print it. After exploring one branch, pop the appended number and clear used[x], restoring exactly the state that existed before that choice. A forgotten undo contaminates later branches, causing omissions or invalid repeated elements.

2. 2. Distinguish ordered and unordered objects

   A permutation orders all n numbers, so [1,2] differs from [2,1]. A subset only decides whether each number is present. The subset function branches into exclusion and inclusion for each x, and includes the empty subset. Choosing numbers in increasing decision order avoids printing the same set under multiple orders.

3. 3. Generate k-combinations without duplicates

   A combination chooses exactly k distinct numbers, with order irrelevant. After choosing x, recurse with start=x+1, so selected values strictly increase. If needed numbers remain, the largest allowed next choice is n−needed+1. A larger next choice would leave too few candidates, so skipping it is sound pruning rather than a guess.

4. 4. Trace n=2,k=1

   Permutations are [1,2] and [2,1]. With exclusion explored first, subsets appear as empty, [2], [1], [1,2]. One-element combinations are [1] and [2]. These orders follow the function call choices; a different traversal order could enumerate the same mathematical answers. The program prints headings to separate the three independent examples.

5. 5. Respect output-size limits

   There are n! permutations, 2ⁿ subsets and C(n,k) combinations. Printing every object already takes time proportional to its written length, so no implementation can output a huge family in constant time. Limit n to 8 here. For decision problems, you may stop after finding a witness; for counting, DP or combinatorics can sometimes avoid listing everything. Pruning must be proven from constraints, not from a branch merely looking unpromising.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
void print(const std::vector<int>&a){
    if(a.empty()){
        std::cout<<"EMPTY\n";
        return;
    }
    for(int i=0;i<(int)a.size();++i){
        std::cout<<a[i]<<(i+1==(int)a.size()?'\n':' ');
    }
}
void permutations(int n,std::vector<int>&path,std::vector<bool>&used){
    if((int)path.size()==n){
        print(path);
        return;
    }
    for(int x=1;x<=n;++x){
        if(!used[x]){
            used[x]=true;
            path.push_back(x); // Choose.
            permutations(n,path,used); // Explore.
            path.pop_back();
            used[x]=false; // Undo both parts of the choice.
        }
    }
}
void subsets(int x,int n,std::vector<int>&path){
    if(x>n){
        print(path);
        return;
    }
    subsets(x+1,n,path); // Exclude x.
    path.push_back(x);
    subsets(x+1,n,path);
    path.pop_back(); // Include and undo.
}
void combinations(int start,int n,int k,std::vector<int>&path){
    int needed=k-(int)path.size();
    if(needed==0){
        print(path);
        return;
    }
    for(int x=start;x<=n-needed+1;++x){ // Enough numbers must remain.
        path.push_back(x);
        combinations(x+1,n,k,path);
        path.pop_back();
    }
}
int main(){
    int n,k;
    std::cin>>n>>k;
    std::vector<int>path;
    std::vector<bool>used(n+1,false);
    std::cout<<"PERMUTATIONS\n";
    permutations(n,path,used);
    std::cout<<"SUBSETS\n";
    subsets(1,n,path);
    std::cout<<"COMBINATIONS\n";
    combinations(1,n,k,path);
}

Complexity analysis

Including output, O(n·n! + n·2ⁿ + n·C(n,k) + n) is a safe bound for all three enumerations; special empty outputs are included in the final term. O(n) working storage holds path, used flags and recursion depth; output is streamed. The answer family itself can be enormous despite linear working memory.

Example input and output

Read n k, 0≤k≤n≤8. Print all permutations, subsets and k-combinations of 1..n in the documented traversal order; print EMPTY for an empty object.

Input

2 1

Output

PERMUTATIONS
1 2
2 1
SUBSETS
EMPTY
2
1
1 2
COMBINATIONS
1
2

The permutation function chooses first elements in increasing order; subset recursion excludes each next value first.

Practical applications

Use for enumerating manageable arrangements or finding solutions under local constraints. Brute force may be simpler if all candidates can be checked independently. Memoization helps only when different paths lead to equivalent subproblems whose remaining results can be reused. More advanced search techniques need additional reasoning.

Check your understanding

Why must a backtracking choice be undone?

Put it into practice

Generate only permutations where adjacent values never differ by one.