How to use the backtracking algorithm in C++

How to use the backtracking algorithm in C

The backtracking algorithm is an algorithm that solves a problem by trying all possible solutions. It is often used to solve combinatorial problems, where the goal is to find all possible combinations that satisfy a set of constraints.

Take the permutation problem as an example. Suppose there is an array nums, and we need to find all possible permutations in it. The following will introduce how to use the backtracking algorithm to solve this problem through a C code example.

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<bool>& visited, vector<int>& permutation) {
    // 如果当前排列的长度等于数组长度，说明已经找到一种解法
    if (permutation.size() == nums.size()) {
        res.push_back(permutation);
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        // 如果当前数字已经被访问过，跳过继续下一次尝试
        if (visited[i]) {
            continue;
        }
        
        // 将当前数字添加到排列中
        permutation.push_back(nums[i]);
        visited[i] = true;
        
        // 继续尝试下一个数字
        backtrack(nums, res, visited, permutation);
        
        // 回溯，从排列中移除当前数字，重新标记为未访问状态
        permutation.pop_back();
        visited[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<bool> visited(nums.size(), false);
    vector<int> permutation;
    backtrack(nums, res, visited, permutation);
    return res;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res = permute(nums);
    
    // 打印结果
    for (vector<int> permutation : res) {
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << endl;
    }
    
    return 0;
}

Run the above code, the output result is:

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

In the above code, we use the backtracking algorithm to solve the arrangement problem. The backtracking function backtrack tries all possible permutations through a depth-first search, while using the visited array to mark the visited numbers to avoid duplication. When the length of the permutation is equal to the length of the array, the current permutation is added to the result.

Through this example, we can see that the core idea of ​​the backtracking algorithm is to try all possible solutions and backtrack when the solution does not meet the conditions. In actual applications, some optimizations can be performed according to the requirements of specific problems, such as pruning operations to reduce unnecessary attempts. The backtracking algorithm has powerful solving capabilities in many combinatorial problems. For beginners, mastering the backtracking algorithm is very beneficial.

The above is the detailed content of How to use the backtracking algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!