初遇DFS

1. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例:输入：s = "abc"输出：["abc","acb","bac","bca","cab","cba"]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

每个位置和其他所有位置都交换一次，但是交换时是相同字符得话则不交换；

Q: 用DFS需搞清递归的参数如何设置？结束条件是啥？

A: 从第一位置开始交换，以下标作为dfs的深度，超过字符串的长度就结束; 如果无重复就交换一次，深度+1

实现

class Solution {
private:
    vector<string> ans;
public:
    vector<string> permutation(string s) {
        dfs(s, 0);
        return ans;
    }
    void dfs(string s, int pos){
        if(pos == s.size()){
            ans.push_back(s);
            return;
        }
        for(int i = pos; i < s.size(); i++){
            if(non_repeat(s, pos, i)){
                swap(s[pos], s[i]);
                dfs(s, pos + 1);
                swap(s[pos], s[i]);
            }
        }
    }
    bool non_repeat(string s, int start, int end){
        for(int i = start; i < end; i++){
            if(s[i] == s[end]) return false;
        }
        return true;
    }
};

2. 24点游戏

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
示例 1:
输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
示例 2:
输入: [1, 2, 1, 2]
输出: False
注意:
除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的 。你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/24-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

从4张牌里面进行选择，每次由2张牌合为一张牌，进行下一轮处理，所以总共有3轮。
第一轮：从4张牌里面任意选两个进行4种操作，
第二轮：从3张牌里面任意选两个进行4种操作，
第三轮：从2张牌选两个进行4中操作

可能的选择和操作总数: (12 * 4) * (6 * 4) * (2 * 4) = 9216种
12 * 4 就是4张牌里面任意选前2个数的组合，这两个数字进行4种操作
6 * 4 就是3张牌里面任意选前2个数的组合，这两个数字进行4种操作
2 * 4 就是2张牌里面任意选前2个数的组合，已经4种操作后的结果。

剪枝: 乘法和加法具有交换律
Q: 以什么作为dfs的参数?
A: 将中间运算结果保存看作未选择的虚拟点数牌, 以未参与运算的牌作为参数, 当还剩一张牌的时候判断是不是24点并返回.
如果不是24点, 注意回溯到之前的状态

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> remaining; // 除法运算需要将int转换为double
        for(int i = 0; i < nums.size(); i++){
            remaining.push_back(double(nums[i]));
        }
        return game(remaining);
    }
    bool game(vector<double> remaining){
        // 结束条件
        if(remaining.size() == 1) return abs(remaining[0] - 24) < 1e-6 ;
        for(int i = 0; i < remaining.size(); i++){
            for(int j = 0; j < remaining.size(); j++){
                vector<double> left;
                if(i != j){  // 
                    // 找到当前排列下的其他元素
                    for(int k = 0; k < remaining.size(); k++){
                        if(k != i && k != j) left.push_back(remaining[k]);       
                    }
                    // ops: 0 + ; 1 * ; 2 - ; 3 /
                    for(int ops = 0; ops < 4; ops++){
                        if(ops < 2 && i > j) continue; // 可交换； 剪枝
                        switch(ops){
                            case 0: left.push_back(remaining[i] + remaining[j]); break;
                            case 1: left.push_back(remaining[i] * remaining[j]); break;
                            case 2: left.push_back(remaining[i] - remaining[j]); break;
                            case 3: 
                            if(remaining[j] != 0) left.push_back(remaining[i] / remaining[j]);
                            break;
                        }
                        if(ops == 3 && remaining[j] == 0) continue;
                        if(game(left)) return true;
                        // 不满足要求则回溯之前的状态
                        left.pop_back();
                    }
                }               
            }
        }
        return false;
    }
};