Leecode77 组合

77. 组合 - 力扣（LeetCode）

算法复习：回溯

回溯模板：

void func( flag, mem, cur)

resType in(){

func(initflag,initmem,cur)

}

题目分析

  1. 组合具有唯一性
  2. 组合内数字不重复
  3. 各个组合内的数字各不相同，不存在组合不同组合内部数字相同的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    void get_combaition(vector<int>& cur, int index, vector<vector<int>>& res,
                        int count, bool* arr, int n, int k) {
        if (count == k) {
            res.push_back(cur);
            return;
        }
        if (index > n)
            return;

        for (int i = index; i <= n; i++) {
            if (arr[i] == 0) {
                cur.push_back(i);
                arr[i] = 1;
                count++;
                get_combaition(cur, i + 1, res, count, arr, n, k);
                cur.pop_back();
                arr[i] = 0;
                count--;
            }
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> cur;
        bool arr[n + 1];
        memset(arr, 0, n + 1);
        get_combaition(cur, 1, res, 0, arr, n, k);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// ACM模式

#include<bits/stdc++.h>
using namespace std;

 int n;
 int k;


void get_combaition(vector<int> &cur,int index,vector<vector<int>> &res,int count, bool *arr,int n,int k){
	if(count==k) {
		res.push_back(cur);
		return;
	}
	if(index>n ) return ;
	
	for(int i = index;i<=n;i++){
		if(arr[i] == 0){
			cur.push_back(i);
		    arr[i] = 1;
			count++;
		    get_combaition(cur,i+1,res,count,arr,n,k);	
			cur.pop_back();
			arr[i] = 0;
			count--;
		}
	}
}

vector<vector<int>> get_res(int n,int k){
	vector<vector<int>> res;
	vector<int> cur;
//	vector<int> arr(n+1,0);
	bool arr[n+1];
	memset(arr,0,n+1);
	get_combaition(cur,1,res,0,arr,n,k);
	return res;
}




int main(){
	int n,k;
	cin>>n>>k;
//	get_res(n,k);	
//	std::cout<<count;
	// 方法二
	vector<vector<int>> res = get_res(n,k);
	for(auto it:res){
		for(auto it2:it){
			cout<<it2<<" ";
		}
		cout<<endl;
	}
	
	
	
	return 0;
}