Permutation & Combination & Subsets

Posted on | In |

Permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
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
public:
    string getPermutation(int n, int k) {
        vector<vector<int>> all;
        vector<int> one;
        vector<int> set;
        for(int i=1;i<=n;i++)
            set.push_back(i);
        dfs(set,all,0);
        sort(all.begin(),all.end());
        string str="";
        for(int i=0;i<n;i++)
        {
            str+=char(all[k-1][i]+48);
        }
        return str;
    }
private:
    void dfs(vector<int>& nums,vector<vector<int>>& result,int cur)
    {
        if(cur==nums.size())
        {
            result.push_back(nums);
            return;
        }
        for (int i = cur; i < nums.size(); i++) {
		    swap(nums[cur], nums[i]);
		    dfs(nums, result,cur + 1);
		    // reset
		    swap(nums[cur], nums[i]);
		}
    }

Combinations

1
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
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
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int>group;
        if(n<k)
            return res;
        combine(res,group,n,k,0,0);
        return res;

    }
private:
    void combine(vector<vector<int>>& res,vector<int>& group,int n,int k,int start,int num)
    {
        if(num==k)
        {
            res.push_back(group);
            return;
        }
        for(int i=start;i<n;++i)
        {
            group.push_back(i+1);
            combine(res,group,n,k,i+1,num+1);
            group.pop_back();
        }
    }
};

Subsets

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
#include<stdio.h>
void subsets(int a[],int b[],int cur,int n);
int main()
{
	int a[]={1,2,3,4,5};
	int b[]={0,0,0,0,0};
	subsets(a,b,0,5);
	return 0;
}

void subsets(int a[],int b[],int cur,int n)
{
	if(cur==5){
	for(int i=0;i<n;++i)
	{
		if(b[i])
		printf("%d ",a[i]);
	}
	printf("\n");
	return;
	}
	b[cur]=1;
	subsets(a,b,cur+1,n);
	b[cur]=0;
	subsets(a,b,cur+1,n);
}
Donate comment here