排列组合

1. 全排列

原理：假设要求的是5个数字的全排列，那么就等同于将第一位数字设置好后加上剩余4个数字的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int vis[30];
    void f(int dep, vector<int>&nums,vector<vector<int>>&ans) {
        if (dep == nums.size()) {
           ans.emplace_back(nums);
           return;
        }
        for (int i = dep;i < nums.size();i++) {
            swap(nums[dep],nums[i]);
            f(dep+1,nums,ans);
            swap(nums[dep],nums[i]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>ans;
        vector<int>temp;
       f(0,nums,ans);
       return ans;
    }
};

2. 组合

求解从n个数里面取出k个数字的可能组合

从1开始，后面的数字等于前面的数字，当数到某个数字的时候对其进行+1，如果此时的值大于n,那么此时需要返回到上一个数字，最终就是从后向前不断使用大的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>>ans;
        vector<int>v(k, 0);
        int i = 0;
        while (i >= 0) {
            /* code */
            v[i]++;
            if (v[i] > n) i--;
            else if (i == k-1) ans.push_back(v);
            else {
                ++i;
                v[i] = v[i-1];
            }
        }
        return ans;
    }
};