回溯法求一个集合的所有子集_回溯以查找所有子集

短命女 2023-03-05 12:35 37阅读 0赞

回溯法求一个集合的所有子集

**Description:**

**描述：**

This is a standard interview problem to find out the subsets of a given set of numbers using backtracking.

这是一个标准的面试问题，它使用回溯来找出给定数字集的子集。

**Problem statement:**

**问题陈述：**

There is a set contains **N** number of elements. You have to find out all the possible subsets of the given set and print them.

有一个包含**N**个元素的集合。 您必须找出给定集合的所有可能子集并进行打印。

Input:
        Test case T
        //T no. of lines with the value of N and corresponding values.
        E.g.
        2
        
        4
        1 2 3 4
    	
        2 
        7 8
    
        1<=T<=100
        1<=N<=1000 
    
        Output:
        Print the subsets of the set.

**Example**

**例**

T=2
    
        Input:
        N=4
        1 2 3 4
        
        Output: 
        1 2
        1 2 3
        1 2 3 4
        1 2 4
        1 3
        1 3 4
        1 4
        2
        2 3
        2 3 4
        2 4
        3
        3 4
        4
        
        Input:
        N=2 
        7 8 
        
        Output:
        7
        7 8
        8

**Explanation with example**

**举例说明**

Let, there is a Set S having N number of elements,

假设有一个N个元素的Set S，

S = {X1, X2, X3, ..., Xn}

The process to print the subsets of the set is a problem of combination and permutation. To get the result we use the backtracking process.

打印集合子集的过程是组合和排列的问题。 为了获得结果，我们使用了回溯过程。

Let,
        f(i) = function to insert the ith number into a subset.

Here, we take a subset of that set in our consideration and consider two things,

在这里，我们考虑一下该集合的子集，并考虑两件事，

1.  An element is a part of that subset ( *f(i)* ).
    
    元素是该子集( *f(i)* )的一部分。
2.  An element is not a part of that subset ( *not f(i)* ).
    
    元素不是该子集的一部分( *不是f(i)* )。

For: N=3
        S = { 1 2 3 }

![Backtracking to find all subsets][]

**Algorithm:**

**算法：**

Here we use the vector STL to store the subsets.

在这里，我们使用向量STL来存储子集。

traverse(arr, n, current_pos,set,subset){
            if(Current_pos is greater or equals to the n)Then
                return
            end if
            for i = current_pos to the end of the set
                insert the element of arr[i] into subset
                insert the subset into the set
                traverse(arr,n,i+1,set,subset)
                pop the element from subset
            end for
        }

**C++ implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    void traverse(int* arr, int n, int pos, vector<vector<int> >& v, vector<int> vi)
    {
        
        //if the current position is greater than or equals to n
        if (pos >= n)
            return;
        for (int i = pos; i < n; i++) {
        
            vi.push_back(arr[i]);
            v.push_back(vi);
            traverse(arr, n, i + 1, v, vi);
            vi.pop_back();
        }
    }
    
    vector<vector<int> > find_subset(int* arr, int n)
    {
        
        vector<vector<int> > v;
        vector<int> vi;
        int pos = 0;
        traverse(arr, n, pos, v, vi);
        return v;
    }
    
    void print(vector<vector<int> > v)
    {
        
        for (int i = 0; i < v.size(); i++) {
        
            for (int j = 0; j < v[i].size(); j++) {
        
                cout << v[i][j] << " ";
            }
            cout << endl;
        }
    }
    
    int main()
    {
        
        int t;
    
        cout << "Test Case : ";
        cin >> t;
    
        while (t--) {
        
            int n;
    
            cout << "Enter the value of n : ";
            cin >> n;
    
            int arr[n];
    
            //taking the set elements
            cout << "Enter the values : ";
            for (int i = 0; i < n; i++) {
        
                cin >> arr[i];
            }
    
            vector<vector<int> > v = find_subset(arr, n);
    
            //print the vector
            print(v);
        }
        return 0;
    }

**Output**

**输出量**

Test Case : 2
    Enter the value of n : 4
    Enter the values : 1 2 3 4
    1
    1 2
    1 2 3
    1 2 3 4
    1 2 4
    1 3
    1 3 4
    1 4
    2
    2 3
    2 3 4
    2 4
    3
    3 4
    4
    Enter the value of n : 2
    Enter the values : 7 8
    7
    7 8
    8

> 翻译自: [https://www.includehelp.com/icp/backtracking-to-find-all-subsets.aspx][https_www.includehelp.com_icp_backtracking-to-find-all-subsets.aspx]

回溯法求一个集合的所有子集

[Backtracking to find all subsets]: https://www.includehelp.com/icp/Images/backtracking-to-find-all-subsets.jpg
[https_www.includehelp.com_icp_backtracking-to-find-all-subsets.aspx]: https://www.includehelp.com/icp/backtracking-to-find-all-subsets.aspx