首页 > itarticle > permutation & combination & subsets

permutation & combination & subsets

admin 11月 14, 2020 0

Permutation

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.

public:
    string (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);
		    
		    swap(nums[cur], nums[i]);
		}
    }

Combinations

1	Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

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


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);
}