Created by potrace 1.14, written by Peter Selinger 2001-2017 Zorch's Blog

回溯,深度优先搜索,记忆化搜索力扣题型总结

 
Category： DSA
  • zorchp
  • 2023年 04月24日

组合类回溯

  1. 77. 组合 - 力扣（LeetCode）;剑指 Offer II 080. 含有 k 个元素的组合;

    class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> path{};
        vector<vector<int>> ans{};
     
        function<void(int)> f = [&](int start) {
            if (path.size() == k) {
                ans.emplace_back(path);
                return;
            }
            // 剪枝: 考虑**还需要**选取的元素个数
            for (int i{start}; i <= n - (k - path.size()) + 1; ++i) {
            // for (int i{start}; i <= n; ++i) {
                path.emplace_back(i);
                f(i + 1);
                path.pop_back();
            }
        };
        f(1);
        return ans;
    }
};

  2. 216. 组合总和 III - 力扣（LeetCode）;

    class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans{};
        vector<int> path{};
        int used[9]{}, sum{};
        function<void()> f = [&]() {
            if (path.size() == k && sum == n) {
                ans.emplace_back(path);
                return;
            }
            for (int i{1}; i <= 9; ++i) {
                if (used[i - 1]) break;
                path.emplace_back(i);
                sum += i;
                used[i - 1] = 1;
                f();
                path.pop_back();
                used[i - 1] = 0;
                sum -= i;
            }
        };
        f();
        return ans;
    }
};

    剪枝, 优化一下(不使用额外数组):

    class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans{};
        vector<int> path{};
        int sum{};
        function<void(int)> f = [&](int start) {
            if (sum > n) return; // 剪枝
            if (path.size() == k && sum == n) {
                ans.emplace_back(path);
                return;
            }
            // 剪枝
            for (int i{start}; i <= 9 - (k - path.size()) + 1; ++i) {
                if (sum + i > n) break; // 剪枝
                path.emplace_back(i);
                sum += i;
                f(i + 1);
                path.pop_back();
                sum -= i;
            }
        };
        f(1);
        return ans;
    }
};

  3. 17. 电话号码的字母组合 - 力扣（LeetCode）;

    class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        unordered_map<char, string> dic{
            {'2', "abc"}, {'3', "def"},  {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
        vector<string> ans{};
        string path{};
     
        function<void(int)> f = [&](int d) {
            if (path.size() == digits.size()) {
                ans.emplace_back(path);
                return;
            }
            for (char c : dic[digits[d]]) {
                path.push_back(c);
                f(d + 1);
                path.pop_back();
            }
        };
        f(0);
        return ans;
    }
};

  4. 39. 组合总和 - 力扣（LeetCode）;

    class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int n = candidates.size(), sum{};
        vector<int> path{};
        vector<vector<int>> ans{};
        sort(candidates.begin(), candidates.end());
     
        function<void(int)> f = [&](int start) {
            if (sum == target) {
                ans.emplace_back(path);
                return;
            }
            for (int i{start}; i < n && candidates[i] + sum <= target; ++i) {
                path.emplace_back(candidates[i]);
                sum += candidates[i];
                f(i);
                path.pop_back();
                sum -= candidates[i];
            }
        };
        f(0);
        return ans;
    }
};

  5. 40. 组合总和 II - 力扣（LeetCode）;

    class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        int n = candidates.size(), sum{};
        vector<int> path{}, used(n);
        vector<vector<int>> ans{};
        sort(candidates.begin(), candidates.end());
     
        function<void(int)> f = [&](int start) {
            if (sum == target) {
                ans.emplace_back(path);
                return;
            }
            for (int i{start}; i < n && candidates[i] + sum <= target; ++i) {
                if (i && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
                path.emplace_back(candidates[i]);
                sum += candidates[i];
                used[i] = 1;
                f(i + 1);
                path.pop_back();
                sum -= candidates[i];
                used[i] = 0;
            }
        };
        f(0);
        return ans;
    }
};

分割问题

可以转化为组合型回溯.

  1. 131. 分割回文串 - 力扣（LeetCode）;剑指 Offer II 086. 分割回文子字符串;

    class Solution {
public:
    vector<vector<string>> partition(string s) {
        auto isPalindrome = [&](int l, int r) {
            for (; l < r; ++l, --r)
                if (s[l] != s[r]) return false;
            return true;
        };
        vector<vector<string>> ans{};
        vector<string> path{};
        int n = s.size();
        function<void(int)> f = [&](int start) {
            if (start == n) {
                ans.emplace_back(path);
                return;
            }
            for (int i{start}; i < n; ++i) {
                if (!isPalindrome(start, i)) continue;
                path.emplace_back(s.substr(start, i - start + 1));
                f(i + 1);
                path.pop_back();
            }
        };
        f(0);
        return ans;
    }
};

    还可以用动态规划预处理数组: (降低复杂度, 上面的解法每次都要判断是否为回文, 存在重复计算)

    class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        bool f[n][n]; // 记录s[i:j]是否为回文
        memset(f, true, sizeof(f));
        vector<vector<string>> ans;
        vector<string> path;
        function<void(int)> dfs = [&](int i) {
            if (i == n) {
                ans.emplace_back(path);
                return;
            }
            for (int j{i}; j < n; ++j) {
                if (f[i][j]) {
                    path.emplace_back(s.substr(i, j - i + 1));
                    dfs(j + 1);
                    path.pop_back();
                }
            }
        };
        for (int i{n - 1}; i >= 0; --i)
            for (int j{i + 1}; j < n; ++j)
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
        dfs(0);
        return ans;
    }
};

  2. 93. 复原 IP 地址 - 力扣（LeetCode）; 剑指 Offer II 087. 复原 IP ;

    class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int n = s.size();
        if (n > 12) return {};
        vector<string> ans{};
        // 判断分隔开的`数字`是否满足IP地址的条件
        auto check = [&](int l, int r) {
            if (l > r) return false;                 // 区间不成立
            if (s[l] == '0' && l != r) return false; // 含有前导零
            int num{};
            for (int i{l}; i <= r; ++i) {
                if (s[i] < '0' || s[i] > '9') return false; // 非数字
                num = 10 * num + s[i] - '0';
                if (num > 255) return false;
            }
            return true;
        };
        int pointNum{};
        function<void(int)> f = [&](int start) {
            if (pointNum == 3) {
                if (check(start, n - 1)) ans.emplace_back(s);
                return;
            }
            for (int i{start}; i < n; ++i) {
                if (check(start, i)) {
                    s.insert(s.begin() + i + 1, '.');
                    ++pointNum, ++n;
                    f(i + 2); // 还要略过加的`.`
                    s.erase(s.begin() + i + 1);
                    --pointNum, --n;
                } else
                    break;
            }
        };
        f(0);
        return ans;
    }
};

  3. 698. 划分为k个相等的子集;($\bigstar$)

 ```cpp
 class Solution {
 public:
     bool canPartitionKSubsets(vector<int>& nums, int k) {
         int sum = accumulate(nums.begin(), nums.end(), 0), n = nums.size();
         if (sum % k) return false;
         int target = sum / k, dp[n];
         memset(dp, 0, sizeof(dp));
         sort(nums.begin(), nums.end(), greater<>());
         function<bool(int)> f = [&](int x) {
             if (x == n) return true;
             for (int i{}; i < k; ++i) {
                 if (i && dp[i] == dp[i - 1]) continue; // 剪枝
                 dp[i] += nums[x];
                 if (dp[i] <= target && f(x + 1)) return true;
                 dp[i] -= nums[x];
             }
             return false;
         };
         return f(0);
     }
 };
 ```
  1. 473. 火柴拼正方形; (上一个题代码拿来改改还能用) 奇安信笔试考了, 就是拼 一个正方形的最大面积
 ```cpp
 class Solution {
 public:
     bool makesquare(vector<int>& nums) {
         int sum = accumulate(nums.begin(), nums.end(), 0), n = nums.size();
         if (sum % 4 || n < 4) return false;
         int target = sum / 4, dp[n];
         memset(dp, 0, sizeof(dp));
         sort(nums.begin(), nums.end(), greater<>());
         function<bool(int)> f = [&](int x) {
             if (x == n) return true;
             for (int i{}; i < 4; ++i) {
                 if (i && dp[i] == dp[i - 1]) continue;
                 dp[i] += nums[x];
                 if (dp[i] <= target && f(x + 1)) return true;
                 dp[i] -= nums[x];
             }
             return false;
         };
         return f(0);
     }
 };
 ```
  1. 2698. 求一个整数的惩罚数 - 力扣（LeetCode）; 有点像复原 ip 地址的感觉, 需要回溯找, 这个回溯跟前面的分割类问题不太一样, 回溯隐藏在递归参数中
 ```cpp
 ```

排列类回溯: 计入顺序

  1. 46. 全排列 - 力扣（LeetCode）;

    class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<int> path{}, used(n);
        vector<vector<int>> ans{};
             
        function<void()> f = [&]() {
            if (path.size() == n)
                ans.emplace_back(path);
            for (int i{}; i < n; ++i) {
                if (used[i]) continue;
                path.emplace_back(nums[i]);
                used[i] = 1;
                f();
                path.pop_back();
                used[i] = 0;
            }
        };
        f();
        return ans;
    }
};

  2. 47. 全排列 II - 力扣（LeetCode）;(可重复排列, 注意去重)

    class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> path{}, used(n);
        vector<vector<int>> ans{};
             
        function<void()> f = [&]() {
            if (path.size() == n)
                ans.emplace_back(path);
     
            for (int i{}; i < n; ++i) {
                if(used[i]) continue;
                if(i && nums[i] == nums[i - 1] && !used[i - 1]) continue;
                path.emplace_back(nums[i]);
                used[i] = 1;
                f();
                path.pop_back();
                used[i] = 0;
            }
        };
        f();
        return ans;
    }
};

  3. 剑指 Offer 17. 打印从1到最大的n位数;

    class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> ans{};
        int num{};
        function<void(int, int)> f = [&](int d, int len) {
            if (d == len) {
                ans.emplace_back(num);
                return;
            }
            // d=0, 从 1 开始, d=1从 0 开始
            for (int i{d == 0}; i <= 9; ++i) {
                num = num * 10 + i;
                f(d + 1, len);
                num /= 10;
            }
        };
        for (int i{}; i < n; ++i) f(0, i + 1);
        return ans;
    }
};

  4. 95. 不同的二叉搜索树 II;

    很经典的二叉搜索树生成题, 用结果数组充当回溯的对象, 每次遍历就相当于回溯过程了(不需要 pop_back).

    class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        function<vector<TreeNode*>(int, int)> f = [&](int l, int r) {
            if (l > r) return vector<TreeNode*>{nullptr};
            vector<TreeNode*> ans{};
            for (int i{l}; i <= r; ++i)
                for (auto lt : f(l, i - 1))
                    for (auto rt : f(i + 1, r))
                        ans.emplace_back(new TreeNode(i, lt, rt));
            return ans;
        };
        return f(1, n);
    }
};

子集类回溯

其实就是组合的一个变种, 不需要记录顺序.

  1. 剑指 Offer II 079. 所有子集 - 力扣（LeetCode）;78. 子集 - 力扣（LeetCode）;

    class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path{};
        vector<vector<int>> ans{};
        int n = nums.size();
     
        function<void(int)> f = [&](int start) {
            ans.emplace_back(path); // 无条件, 直接记录
            for (int i{start}; i < n; ++i) {
                path.emplace_back(nums[i]);
                f(i + 1);
                path.pop_back();
            }
        };
        f(0);
        return ans;
    }
};

  2. 90. 子集 II - 力扣（LeetCode）;(注意去重逻辑)

    class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int n = nums.size();
        vector<int> path{}, used(n);
        vector<vector<int>> ans{};
        sort(nums.begin(), nums.end());
     
        function<void(int)> f = [&](int start) {
            ans.emplace_back(path);
            for (int i{start}; i < n; ++i) {
                if (i && !used[i - 1] && nums[i] == nums[i - 1]) continue;
                path.emplace_back(nums[i]);
                used[i] = 1;
                f(i + 1);
                path.pop_back();
                used[i] = 0;
            }
        };
        f(0);
        return ans;
    }
};

子序列类回溯

  1. 491. 递增子序列;

    class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> path{};
        vector<vector<int>> ans{};
        int n = nums.size();
     
        function<void(int)> f = [&](int start) {
            if (path.size() > 1)
                ans.emplace_back(path);
     
            unordered_set<int> uset{};
            for (int i{start}; i < n; ++i) {
                if ((!path.empty() && nums[i] < path.back()) || uset.count(nums[i]))
                    continue;
                path.emplace_back(nums[i]);
                uset.insert(nums[i]);
                f(i + 1);
                path.pop_back();
            }
        };
        f(0);
        return ans;
    }
};

    用数组哈希也可以: (由于数据范围小)

    class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> path{};
        vector<vector<int>> ans{};
        int n = nums.size();
     
        function<void(int)> f = [&](int start) {
            if (path.size() > 1)
                ans.emplace_back(path);
     
            int uset[201]{};
            for (int i{start}; i < n; ++i) {
                if ((!path.empty() && nums[i] < path.back()) || uset[nums[i] + 100])
                    continue;
                path.emplace_back(nums[i]);
                uset[nums[i] + 100] = 1;
                f(i + 1);
                path.pop_back();
            }
        };
        f(0);
        return ans;
    }
};

综合题

这里需要考虑二维数组上的回溯, 以及树上的回溯问题

矩阵中的路径

79. 单词搜索;剑指 Offer 12. 矩阵中的路径;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size(), ws = word.size();
        int ds[]{1, 0, -1, 0, 1};
        bool vs[m][n];
        memset(vs, 0, sizeof(vs));
        function<bool(int, int, int)> f = [&](int x, int y, int idx) {
            if (board[x][y] != word[idx]) // 剪枝
                return false;
            else if (idx == ws - 1)
                return true;
            bool flg{};
            vs[x][y] = true;
            for (int i{}; i < 4; ++i) {
                int nx{x + ds[i]}, ny{y + ds[i + 1]};
                if (nx < 0 || ny < 0 || nx >= m || ny >= n || vs[nx][ny])
                    continue;
                if (f(nx, ny, idx + 1)) {
                    flg = true;
                    break;
                }
            }
            vs[x][y] = false; // 回溯
            return flg;
        };
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (f(i, j, 0))
                    return true;
        return false;
    }
};

树上回溯问题

113. 路径总和 II - 力扣（Leetcode）;

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> ans;
        vector<int> path;
        function<void(TreeNode*, int)> f = [&](TreeNode* node, int sum) {
            if (!node)
                return;
            sum += node->val;
            path.emplace_back(node->val);
            if (!node->left && !node->right && sum == targetSum)
                ans.emplace_back(path);
            f(node->left, sum);
            f(node->right, sum);
            path.pop_back();
        };
        f(root, 0);
        return ans;
    }
};

重新安排行程

332. 重新安排行程;

class Solution {
    unordered_map<string, map<string, int>> targets;

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        function<bool(int, vector<string>&)> f = [&](int ticketNum,
                                                     vector<string>& res) {
            if (res.size() == ticketNum + 1) return true;
            for (auto& target : targets[res[res.size() - 1]]) {
                if (target.second) {
                    res.emplace_back(target.first);
                    target.second--;
                    if (f(ticketNum, res)) return true;
                    res.pop_back();
                    target.second++;
                }
            }
            return false;
        };
        vector<string> res;
        for (auto& vec : tickets) targets[vec[0]][vec[1]]++;
        res.emplace_back("JFK");
        f(tickets.size(), res);
        return res;
    }
};

N皇后

51. N 皇后;52. N 皇后 II;面试题 08.12. 八皇后;

上面的51和52其实是一个题, 因为第二问只是问数量.

经典回溯题型, 其实跟前面的分割型问题类似, 需要自定义一个判断函数, 然后进入二维循环中进行判断:

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans{};
        vector<string> path(n, string(n, '.'));

        auto isValid = [&](int row, int col) {
            // 检查列中有无皇后
            for (int i{}; i <= row; ++i)
                if (path[i][col] == 'Q') return false;
            for (int i{row - 1}, j{col - 1}; i >= 0 && j >= 0; --i, --j)
                if (path[i][j] == 'Q') return false;
            for (int i{row - 1}, j{col + 1}; i >= 0 && j < n; --i, ++j)
                if (path[i][j] == 'Q') return false;
            return true;
        };

        function<void(int)> f = [&](int row) {
            if (row == n) {
                ans.emplace_back(path);
                return;
            }
            for (int col{}; col < n; ++col) {
                if (!isValid(row, col)) continue;
                path[row][col] = 'Q';
                f(row + 1);
                path[row][col] = '.';
            }
        };
        f(0);
        return ans;
    }
};

对于52题, 只需对ans返回值稍作改动:

class Solution {
public:
    int totalNQueens(int n) { // n in [1,9]
        bitset<9> board[n];
        int ans{};
        auto check = [&](int r, int c) {
            for (int i{}; i < r; ++i)
                if (board[i][c]) return false;
            for (int i{r - 1}, j{c - 1}; i >= 0 && j >= 0; --i, --j)
                if (board[i][j]) return false;
            for (int i{r - 1}, j{c + 1}; i >= 0 && j < n; --i, ++j)
                if (board[i][j]) return false;
            return true;
        };
        function<void(int)> f = [&](int r) {
            if (r == n) {
                ++ans;
                return;
            }
            for (int c{}; c < n; ++c) {
                if (!check(r, c)) continue;
                board[r][c] = 1;
                f(r + 1);
                board[r][c] = 0;
            }
        };
        f(0);
        return ans;
    }
};

不过, bitset看起来还是不够快, 需要经典的位运算技巧了:

class Solution {
public:
    int totalNQueens(int n) { // n in [1,9]
        int board[n];
        memset(board, 0, sizeof(board));
        int ans{};
        auto check = [&](int r, int c) {
            for (int i{}; i < r; ++i)
                if (board[i] & 1 << c) return false;
            for (int i{r - 1}, j{c - 1}; i >= 0 && j >= 0; --i, --j)
                if (board[i] & 1 << j) return false;
            for (int i{r - 1}, j{c + 1}; i >= 0 && j < n; --i, ++j)
                if (board[i] & 1 << j) return false;
            return true;
        };
        function<void(int)> f = [&](int r) {
            if (r == n) {
                ++ans;
                return;
            }
            for (int c{}; c < n; ++c) {
                if (!check(r, c)) continue;
                board[r] |= 1 << c;
                f(r + 1);
                board[r] &= ~(1 << c);
            }
        };
        f(0);
        return ans;
    }
};

简单解释一下:

  • 将n 的第m位设为 1: n |= 1 << m; 1左移 m 位相当于一个仅第 m 位为 1 的数, 此数与 n 进行或运算就是把 n 的第 m 位设为 1
  • 将n 的第m位设为 0: n &= ~(1 << m); 1左移 m 位相当于一个仅第 m 位为 1 的数, 取反表示仅第 m 位为 0, 其余位都为 1 的数, 此数与 n 进行与运算就是把 n 的第 m 位设为 0, 并且不改变其他位置的值
  • 取出n的第m位: n & 1 << m; 1左移 m 位相当于一个仅第 m 位为 1 的数, 此数与 n 进行与运算就是取出了 n 的第 m 位, 因为只有 n 的第 m 位为 1 时与运算的结果才为 1

解数独

37. 解数独;

做这道题之前需要先做一下有效数独这个题, 因为需要判断数独的可行性.

36. 有效的数独;

参考了: 双百的JAVA实现，通过Bit位标记;

这个题就是一个模拟, 需要注意取余的时候更新值.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9]{}, col[9]{}, block[3][3]{};
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if ('.' == board[i][j]) continue;
                int num = board[i][j] - '1';
                if (row[i] & (1 << num)) return false;
                if (col[j] & (1 << num)) return false;
                if (block[i / 3][j / 3] & (1 << num)) return false;
                col[j] |= 1 << num, row[i] |= 1 << num;
                block[i / 3][j / 3] |= 1 << num;
            }
        }
        return true;
    }
};

然后就是正菜了: 解数独.

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        auto check = [&](int r, int c, int v) {
            for (int i{}; i < 9; ++i)
                if (board[i][c] == v || board[r][i] == v) return false;
            for (int sr{(r / 3) * 3}, i{sr}; i < sr + 3; ++i)
                for (int sc{(c / 3) * 3}, j{sc}; j < sc + 3; ++j)
                    if (board[i][j] == v) return false;
            return true;
        };
        function<bool()> f = [&] { // 注意这里的 bool 返回值用来做剪枝
            for (int r{}; r < 9; ++r)
                for (int c{}; c < 9; ++c) {
                    if (board[r][c] != '.') continue;
                    for (char k{'1'}; k <= '9'; ++k) {
                        if (!check(r, c, k)) continue;
                        board[r][c] = k;
                        if (f()) return true;
                        board[r][c] = '.';
                    }
                    return false;
                }
            return true;
        };
        f();
    }
};

24点游戏

679. 24 点游戏;

这里就不得不提一下我之前写的8个8组成1000的回溯方法了, 这么一想回溯也没有那么难了.

24点游戏回溯算法与8个8组成1000问题c++,java代码; 下面的代码参考: 题解.

class Solution {
public:
    bool judgePoint24(vector<int>& cards) {

        function<bool(vector<double>&)> f = [&](vector<double>& v) {
            int n = v.size();
            if (n == 1) return abs(v[0] - 24) < 1e-4;
            bool ok{};
            for (int i{}; i < n - 1; ++i)
                for (int j{i + 1}; j < n; ++j) {
                    auto a{v[i]}, b{v[j]};
                    vector<double> res;
                    for (int k{}; k < n; ++k)
                        if (k != i && k != j) res.emplace_back(v[k]);
                    res.emplace_back(a + b);
                    ok = ok || f(res); // 利用逻辑或的短路特性, 为真直接返回不做后续判断了
                    res.pop_back();
                    
                    res.emplace_back(a - b);
                    ok = ok || f(res);
                    res.pop_back();

                    res.emplace_back(a * b);
                    ok = ok || f(res);
                    res.pop_back();

                    res.emplace_back(a / b);
                    ok = ok || f(res);
                    res.pop_back();

                    res.emplace_back(b - a);
                    ok = ok || f(res);
                    res.pop_back();

                    res.emplace_back(b / a);
                    ok = ok || f(res);
                    res.pop_back();

                    if (ok) return true;
                }
            return false;
        };
        vector<double> tmp(cards.begin(), cards.end());

        return f(tmp);
    }
};

还有一种比较简洁的方法:

search search_off backspace