Algorithm-DS-Problems/combinations_of_k_digit.cpp at master · ankishb/Algorithm-DS-Problems · GitHub

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

// new program
/*
Note: if we use very first base condition, it will not include last element, in that case you need to use n+1.
    And the reason is that when we push last element n, we start with n+1 in the next iteration, which is greater than n and it miss that.
*/
void helper(int start, int end, int k, vector<vector<int>> &store, vector<int> &temp){
    // if(start > end) return;
    if(temp.size() == k){
        store.push_back(temp);
        return;
    }
    for(int i=start; i<=end; i++){
        temp.push_back(i);
        helper(i+1, end, k, store, temp);
        temp.pop_back();
    }
}

vector<vector<int> > Solution::combine(int n, int k) {
    if(n == 0 || k == 0) return {{}};
    vector<vector<int>> store;
    vector<int> temp;
    helper(1, n, k, store, temp);

    // for(auto v : store){
    //     for(auto el : v){
    //         cout<<el<<" ";
    //     }
    //     cout<<endl;
    // }
    return store;
}


// old interviewBit submit
void rec(int n, int j, int k, vector<vector<int> > &ans, vector<int> &temp){
    if(temp.size() == k){
        ans.push_back(temp);
        return ;
    }
    for(int jj=j; jj<=n; jj++){
        temp.push_back(jj);
        rec(n, jj+1, k, ans, temp);
        temp.pop_back();
    }
}

vector<vector<int> > Solution::combine(int n, int k) {
    vector<int> temp;
    vector<vector<int> > ans;
    rec(n, 1, k, ans, temp);

    return ans;
}


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

void rec(int n, int j, int k, vector<vector<int> > &ans, vector<int> &temp){
    if(temp.size() == k){
        ans.push_back(temp);
        return ;
    }
    for(int jj=j; jj<=n; jj++){
        temp.push_back(jj);
        rec(n, jj+1, k, ans, temp);
        temp.pop_back();
    }
}

void get_all_combination(int n, int k){
    vector<int> temp;
    vector<vector<int> > ans;
    rec(n, 1, k, ans, temp);

    cout<<"\n All combinations \n";
    for(auto itr1:ans){
        for(auto itr2 : itr1){
            cout<<itr2<<" ";
        }
        cout<<endl;
    }
}

int main()
{
	int test;
	cin>>test;
	while(test--){
		int n, k;
        cin>>n>>k;
        get_all_combination(n, k);
	}
	return 0;
}