Home > Backend Development > C++ > Detailed explanation of C++ function recursion: solving combination problems recursively

Detailed explanation of C++ function recursion: solving combination problems recursively

王林
Release: 2024-05-01 10:30:02
Original
971 people have browsed it

Recursion is a method used to solve combinatorial problems where a function calls itself. The algorithm steps include a baseline condition (returning an empty set when the number of elements to be selected is 0) and a recursive step (enumerating all possible combinations and appending the current element). In the actual case, a recursive function is used to solve all possible combinations of selecting 3 numbers from the number set to form a three-digit number.

C++ 函数递归详解:递归求解组合问题

Detailed explanation of C function recursion: recursively solving combination problems

Introduction

Recursion It is a process in which a function calls itself, and it can be used to solve a variety of problems. In this article, we will explore techniques for solving combinatorial problems using recursion.

Combination problem

Combination problem refers to selecting a specific number of elements from a set of elements, regardless of the order of the elements. For example, choose 3 letters from a set to form a word.

Recursive algorithm

We can use recursive functions to solve combinatorial problems. This function accepts two parameters:

  • Element collection
  • The number of elements to be selected

Algorithm steps:

  1. Baseline condition: If the number of elements to be selected is 0, an empty set (that is, a set without any elements) is returned.
  2. Recursive steps:

    • Remove any element from the element set.
    • Call the function recursively on the remaining element set and reduce the number of elements to be selected by 1.
    • Append the current element to the result of the recursive call.

Practical case:

Let us use a recursive function to solve a practical problem:

Question: Select 3 numbers from a set of numbers to form a three-digit number and find all possible combinations.

Solution:

#include <iostream>
#include <vector>

using namespace std;

void findCombinations(vector<int> numbers, int n, int k) {
    if (k == 0) {
        for (int i : numbers) {
            cout << i;
        }
        cout << endl;
    } else {
        for (int i = 0; i < n; i++) {
            numbers.push_back(i);
            findCombinations(numbers, n, k - 1);
            numbers.pop_back();
        }
    }
}

int main() {
    int n; // 元素数量
    int k; // 需要选择的元素数量
    cin >> n >> k;

    vector<int> numbers;
    findCombinations(numbers, n, k);

    return 0;
}
Copy after login

Program description:

  • Enter the number of elements and the number of elements to be selected.
  • Initialize an empty collection to store combinations.
  • Call the recursive function findCombinations, which enumerates all possible combinations and outputs the results.

Execution example:

Input:

5 3
Copy after login

Output:

012
013
014
023
024
034
123
124
134
234
Copy after login

The above is the detailed content of Detailed explanation of C++ function recursion: solving combination problems recursively. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template