【OJ】DFS

$A_n^k$与$C_n^k$（排列与组合）

题目大意：给定两个整数 n 和 k，求$C_n^k$ 。原题链接-力扣77

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

分析

用dfs，数组a[]记录一个组合结果，v[]记录当前数字是否访问过了。

代码

如果没有start参数，即dfs(int n, int k, int c)，并且for循环中的i=start改成i=1，那么就是全排列，也就是$A_n^k$。

为什么呢？因为相当于在每一层中做选择的时候，可选择的数字不再局限于比前一层数字大的数字了，而是可以从所有1~n个数字中选择。

class Solution {
public:
    int a[25],v[25];
    vector<vector<int>> res;  //res保存了所有结果
    /*参数说明
    n和k仅传参用；
    c表示当前已拾取了几个数（当前处在第几层）
    start表示本次拾取从哪个数开始    
    */
    void dfs(int n, int k, int c, int start){
        //终止条件
        if(c==k){
            vector<int> v;
            //a[]中所有数据转移到vector中，保存。
            for(int i=0;i<k;i++) {
                v.push_back(a[i]);
            }
            res.push_back(v); 
            return;
        }
        //横向选择
        for(int i=start;i<=n;i++){  //如果把i=start改成i=1，start参数去掉，则变成全排列
            if(!v[i]){
                v[i]=1;  //标记
                a[c]=i;  //选择
                //层数+1，并且下一层要从该数的下一个数开始拾取。
                dfs(n, k, c+1, i+1);
                v[i]=0;  //取消标记
            }
        }

    }
    vector<vector<int>> combine(int n, int k) {
        memset(a, 0, sizeof(a));
        memset(v, 0, sizeof(v));   
        dfs(n,k,0,1);
        return res;
    }
};

电话号码的字母组合

原题链接-力扣17

题目大意：输入是由数字2-9 组成的字符串，返回对应的手机九键中，所有它能表示的字母组合。答案可以按 任意顺序 返回。

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

分析

选择dfs的理由：

• 对每一位数字，都有几个对应的字母供它选择（横向选择）。
• 逐层递进，直到所有位的数字都选出对应的字母（纵向前进）。

这题没有v[]数字数组，因为每个数字都在不同的几个字母中挑选，不存在选到其他层的字母的问题。此外，记录路径的a[]数组也改用字符串s来记录路径。

class Solution {
public:
    //数字和字母的映射表
    const string letter[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    int num[10];
    int len;
    string s;
    vector<string> res;  //记录所有结果
    void dfs(int c){
        //终止条件
        if(c==len){
            res.push_back(s);
            return;
        }
        //横向选择
        //letter[num[c]]：第ｃ层对应数字所对应的字母表
        for(int i=0; i<letter[num[c]].length(); i++){
            s.push_back(letter[num[c]][i]);　　//选择一个字母加入（相当于标记）
            dfs(c+1);
            s.pop_back(); //退出一个字母（取消标记）
        }
    }
    vector<string> letterCombinations(string digits) {
        //如果字符串为空，也返回空。
        if(digits.length()==0) return {};
        len=digits.length();
        //保存每一位数字
        for(int i=0; i<len; i++){
            num[i] = digits[i]-'0';
        }
        dfs(0);
        return res;
    }
};

ps：string也可以像vector一样用push_back(x)和pop_back()。

组合总和（候选无重复，选取可重复）

原题链接-力扣17

题目大意：给你一个无重复元素的数组 candidates ，找出 candidates 中可以使数字和为 target 的所有不同组合。可以按任意顺序返回这些组合。candidates中的数字可以被重复选取 。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3], [7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

分析

每个数字可以被重复选取，也就不用v[]数组了；对结果的个数没有要求，只要能凑出target都行，所以dfs的参数中也不需要记录当前的层数c了，另外需要添加start参数保证结果是“组合”而非“排列”。这题其实条件很松弛，写起来更简单。

class Solution {
public:
    vector<vector<int>> res;  //记录所有结果
    vector<int> v;  //记录单条结果
    /*candidates：仅是传参。rest：接下来还要凑的总和。start：避免全排列。*/
    void dfs(vector<int>& candidates, int rest, int start){
        //到达非法边界，退出
        if(rest<0) return;
        //满足题意，记录结果后退出
        if(rest==0){
            res.push_back(v);
            return;
        }
        //横向选择
        for(int i=start;i<candidates.size();i++){
            v.push_back(candidates[i]);  //选择
            dfs(candidates, rest-candidates[i], i);  //下一次当前值还能选，所以start=i
            v.pop_back();  //回溯
        }

    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //单刀直入，直接dfs就完事了
        dfs(candidates, target, 0);
        return res;
    }
};

组合总和II（候选有重复，选取无重复）

原题链接-力扣40

题目大意：给你一个有重复元素的数组 candidates ，找出 candidates 中可以使数字和为 target 的所有不同组合。可以按任意顺序返回这些组合。candidates中的数字不可以重复选取 。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出: [[1,1,6],[1,2,5],[1,7],[2,6]]
解释: 虽然candidates数组中有两个1，但是不能输出两次[1,7]。

分析

先对candidates排序，使得相同的元素挨在一起，这样做的目的是为了更容易找到相同的元素，以便于将重复的情况剔除。

与上一题相比，增加了两处关键代码：

• 开始dfs之前，先sort()
• 横向选择时，增加if条件判断：当i>start且candidates[i] == candidates[i-1]时，直接continue，剪掉整个枝

看代码：

class Solution {
public:
    vector<vector<int>> res;  //保存所有结果
    vector<int> vec;  //保存单次结果
    /*candidates: 仅传参。rest: 剩余总和。start: 避免全排列。*/
    void dfs(vector<int>& candidates, int rest, int start){
        if(rest<0) return;
        if(rest==0){
            res.push_back(vec);
            return;
        }
        for(int i=start; i<candidates.size(); i++){
            //关键去重代码：
            if(i>start && candidates[i] == candidates[i-1])
                continue;
            vec.push_back(candidates[i]);
            dfs(candidates, rest-candidates[i], i+1);
            vec.pop_back();
            
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        //先排序
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return res;
    }
};