6 solutions

  • 0
    @ 2025-3-17 17:09:12
    #include <bits/stdc++.h>
    using namespace std;
    
    //递归函数
    void function_Permutation(vector<int>& arr, vector<int>&arrs, size_t start, size_t r, vector<vector<int>>& result) {
        //终止条件 动态数组arrs取了r个数时
        if ( arrs.size() == r ) {
            result.push_back(arrs);//把动态数组放在结果数组里面
            return;
        }
        for ( size_t i = start; i < arr.size(); i++ ) {
            arrs.push_back(arr[i]); //按顺序将每一个数字固定在arrs数组中
            function_Permutation(arr , arrs , i + 1 , r , result); // 递归深入处理选数字找位置(i+1)==》 start
            arrs.pop_back(); // 递归最深处后(代表最后一个数字有了并且存下了,那就删掉最后一个数字进入循环。
            //问题出在 arrs.pop_back(arr[i]) 这一行代码。std::vector::pop_back 是一个成员函数,
            //它的作用是移除向量的最后一个元素,但它不接受任何参数。然而,你在调用时错误地传入了一个参数 arr[i]。
        }
    }
    
    int main() 
    {
        int n,r;
        cin >> n >> r;
        //接收数组
        vector<int> arr(n);
        for ( int i = 0; i < n; i++ ) {
            cin >> arr[i];
        }
        //升序
        sort(arr.begin() , arr.end());
        //创建储存数组result 动态数组arrs
        vector<vector<int>> result;
        vector<int> arrs;
        //调用递归函数
        function_Permutation(arr, arrs , 0 , r , result); 
        //输出结果函数
        for ( const auto& nums : result ) {
            for ( int num : nums ) {
                cout << num << " ";
            }
            cout << endl;
        }
        return 0;
    }
    
    
    • 0
      @ 2024-4-19 16:39:16

      求组合实际上可以不用标记走过,可以利用下标来,往后走就是

      #include<cstdio>
      #include<iostream>
      #include<algorithm> 
      using namespace std;
      int num[12];
      int mstate[12];
      int n,r;
      void dfs(int top,int numi){
      	if(top==r){
      		for(int k=0;k<top-1;++k) cout<<mstate[k]<<" ";
      		cout<<mstate[top-1]<<endl;
      		return;
      	}
      
      	for(int i=numi;i<n;i++){
      		mstate[top]=num[i];
      		dfs(top+1,i+1);
      	}
      	return;
      }
      int main(){
      
      	cin>>n>>r;
      	for(int i=0;i<n;i++) cin>>num[i];
      	sort(num,num+n);
      	dfs(0,0);	
      	return 0;
      	
      }
      

      顺便写了个组合并且全排列,这时候就需要flag记录了

      #include<cstdio>
      #include<iostream>
      #include<algorithm> 
      using namespace std;
      int num[12];
      int flag[12];
      int mstate[12];
      int n,r;
      int mcount=0;
      void dfs(int top){
      	if(top==r){
      		for(int k=0;k<top-1;++k) cout<<mstate[k]<<" ";
      		cout<<mstate[top-1]<<endl;
      		mcount++;
      		return;
      	}
      
      	for(int i=0;i<n;i++){
      		if(flag[i]!=1){
      		
      		mstate[top]=num[i];
      		flag[i]=1;
      		dfs(top+1);
      		flag[i]=0;
      		}
      	}
      	return;
      }
      int main(){
      
      	cin>>n>>r;
      	for(int i=0;i<n;i++) cin>>num[i];
      	sort(num,num+n);
      	dfs(0);
      	cout<<mcount;	
      	return 0;
      	
      }
      
      • 0
        @ 2024-4-11 18:47:51
        #include<bits/stdc++.h>
        #define int long long 
        #define endl '\n'
        using namespace std;
        int n,r;
        int nums[10];
        bool st[10];
        int ans[10];
        bool flag = true;
        void dfs(int accounts){
        	if(accounts == r){
        		for(int i = 0; i < r - 1;i++){
        			if(ans[i] > ans[i+1]){
        			flag = false;
        		}
        		}
        		if(flag == true){
        		for(int i = 0;i < r;i++){
        			cout<<ans[i]<<" ";
        		}
        		cout<<endl;
        	}
        	flag = true;
        		return ;
        	}
        	for(int i = 0;i < n;i++){
        		if(st[i] == false){
        		ans[accounts] = nums[i];
        		st[i] = true;
        		dfs(accounts+1);
        		st[i] = false;
        		}
        	}
        	return ;
        }
        signed main(){
        	ios::sync_with_stdio(0);
        	cin.tie(0);
        	cout.tie(0);
        	cin>>n;
        	cin>>r;
        	for(int i = 0;i < n;i++){
        		cin>>nums[i];
        	}
        	sort(nums,nums+n);
        	dfs(0);
        	return 0;
        }
        
        • 0
          @ 2024-4-10 21:18:54
          import java.util.*;
          
          public class Main {
          	public static boolean flag[];// 标记第i个元素是否被使用过
          	public static int n;
          	public static int road[];
          
          	//用来检查是否是正序的
          	public static boolean check(int road[], int total) {
          		boolean natural = true;
          		for (int i = 1; i < total; i++) {
          			if (road[i] > road[i + 1])
          				natural = false;
          		}
          		return natural;
          	}
          
          	// idx 选择第几个数了
          	// 选取元素总数
          	public static void dfs(int idx, int num[], int total) {
          		if (idx > total) {
          			if (check(road,total)) {
          				for (int i = 1; i <= total; i++) {
          					System.out.print(road[i] + " ");
          				}
          				System.out.println();
          			}
          			return;
          		}
          		for (int i = idx ; i <= n; i++) {
          			if (!flag[i]) {
          				road[idx] = num[i];
          				flag[i] = true;
          				dfs(idx + 1, num, total);
          				flag[i] = false;
          			}
          		}
          		return;
          	}
          
          	public static void main(String[] args) {
          		Scanner sc = new Scanner(System.in);
          		n = sc.nextInt();
          		int r = sc.nextInt();
          
          		flag = new boolean[n + 5];
          		int num[] = new int[n + 5];
          		road = new int[n + 5];
          		for (int i = 1; i <= n; i++) {
          			num[i] = sc.nextInt();
          		}
          //		fromIndex 是排序开始的位置(包含),toIndex 是排序结束的位置(不包含)。
          //		这意味着 Arrays.sort(a, fromIndex, toIndex) 将对数组 a 从索引 fromIndex 到 toIndex - 1 的范围进行排序。
          		Arrays.sort(num, 1, n+1);
          		sc.close();
          		dfs(1, num, r);
          	}
          }
          
          • 0
            @ 2024-4-10 16:33:53
            #include<iostream>
            #include<algorithm>
            #include<cmath>
            #include<cstdio>
            #include<climits>
            #include<vector>
            using namespace std;
            int n,r;
            vector<int> res;
            void dfs(int startIndex,int countNum,int nums[],int used[]){
            //	处理递归终止的条件
            	if(countNum>r){
            		for(auto temp:res) cout<<temp<<" ";
            		cout<<endl;
            		return;
            	}
            //	处理递归的单层逻辑
            	for(int i=startIndex;i<n;i++){
            		if(used[i]==1) continue;
            		used[i]=1;
            		res.push_back(nums[i]);
            		dfs(i+1,countNum+1,nums,used);
            		used[i]=0;	
            		res.pop_back();
            		
            	}
            }
            int main(){
            	cin>>n>>r;
            	int nums[n];
            	int used[n]={0};
            	for(int i=0;i<n;i++) scanf("%d",&nums[i]);
            	sort(nums,nums+n);
            	dfs(0,1,nums,used);//从第一个数开始选
            	return 0;
            }
            
            
            • 0
              @ 2024-4-8 21:16:29

              DFS即可

              #include <bits/stdc++.h>
              using namespace std;
              const int N = 20;
              int a[N];
              int b[N];
              int n,m;
              void dfs(int x,int start){
                  if (x > m) {
                      for (int i = 1; i <= m; ++i) {
                          printf("%d ",b[i]);
                      }
                      printf("\n");
                      return;
                  }
                  for (int i = start; i <= n; ++i) {
                      b[x] = a[i];
                      dfs(x + 1,i + 1);
                  }
              }
              int main(){
                  scanf("%d %d",&n,&m);
                  for (int i = 1; i <= n; ++i) {
                      scanf("%d",&a[i]);
                  }
                  sort(a + 1, a + n + 1);
                  dfs(1,1);
                  return 0;
              }
              
              • 1

              Information

              ID
              83
              Time
              1000ms
              Memory
              256MiB
              Difficulty
              5
              Tags
              # Submissions
              467
              Accepted
              162
              Uploaded By