DFS生成排列组合

生成排列数

P(n, d)： 从所给的N个数从选择d个生成所有的排列。

代码：

vector<vector<int>> Permutations(vector<int>& nums, int d) {
    vector<vector<int>> ans; // 储存排列结果

    vector<int> cur; // 当前排列
    vector<int> used(nums.size(), 0); // 访问数组

    function<void(int)> dfs = [&] (int depth) { // dfs生成所有排列 depth递归深度
        if(depth == d) {
            ans.push_back(cur);
            return;
        }

        for(int i = 0; i < nums.size(); ++i) {
            if(used[i]) continue;
            used[i] = 1;
            cur.push_back(nums[i]);
            dfs(depth + 1);
            cur.pop_back();
            used[i] = 0;
        }
    };

    dfs(0);

    return ans;
}

调用Permutations([1,2,3,4], 2)，运行结果：

12
13
14
21
23
24
31
32
34
41
42
43

生成组合数

C(n, d)： 从所给的N个数从选择d个生成所有的组合。

代码：

vector<vector<int>> Combinations(vector<int>& nums, int d) {
    vector<vector<int>> ans; // 储存组合结果
    vector<int> cur; // 当前组合

    // dfs生成所有组合 depth递归深度 s起始位置
    function<void(int, int)> dfs = [&] (int depth, int s) { 
        if(depth == d) {
            for(int i : cur) cout << i;
            cout << endl;
            ans.push_back(cur);
            return;
        }

        for(int i = s; i < nums.size(); ++i) { // 从s位置开始遍历
            cur.push_back(nums[i]);
            dfs(depth + 1, i + 1);
            cur.pop_back();
        }
    };

    dfs(0, 0);

    return ans;
}

调用Combinations([1,2,3,4], 3)，运行结果：

123
124
134
234