组合

求所有可能性的全集, 一般回溯

回溯有 2 种通常的做法:

递归中遍历选择第 i 个元素;
将第 i 个元素视为选择或者不选择进行递归;

组合全集

17. 电话号码的字母组合 mid

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

经典回溯

java

public class Solution {
    Map<Character, String> map = Map.of(
            '2', "abc",
            '3', "def",
            '4', "ghi",
            '5', "jkl",
            '6', "mno",
            '7', "pqrs",
            '8', "tuv",
            '9', "wxyz"
    );

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.isEmpty()) return res;
        StringBuilder sb = new StringBuilder();
        backtrace(res, sb, digits);
        return res;
    }

    private void backtrace(List<String> res, StringBuilder sb, final String digits) {
        if (sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }
        int curIdx = sb.length();
        String s = map.get(digits.charAt(curIdx));
        for (char c : s.toCharArray()) {
            sb.append(c);
            backtrace(res, sb, digits);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

22. 括号生成 mid

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

回溯, countdown 计数比较方便

java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(n, n, new StringBuilder(), res);
        return res;
    }

    private void backtrack(int n, int m, StringBuilder sb, List<String> res) {
        if (n > m) return;
        if (n == 0 && m == 0) {
            res.add(sb.toString());
            return;
        }
        // 试试 "("
        if (n > 0) {
            sb.append('(');
            backtrack(n - 1, m, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
        // ")" 肯定还剩, 试试 ")"
        sb.append(')');
        backtrack(n, m - 1, sb, res);
        sb.deleteCharAt(sb.length() - 1);
    }
}

39. 组合总和 mid

剑指 Offer II 081. 允许重复选择元素的组合

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

不包含 0

java

class Solution {

    public List<List<Integer>> combinationSum(int[] arr, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(arr);
        this.backtrack(res, arr, target, new LinkedList<>(), 0);
        return res;
    }

    private void backtrack(List<List<Integer>> res, int[] arr, int target, Deque<Integer> list, int start) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            int e = arr[i];
            if (target < e) return;
            list.addLast(e);
            this.backtrack(res, arr, target - e, list, i);
            list.removeLast();
        }
    }
}

40. 组合总和 II mid

剑指 Offer II 082. 含有重复元素集合的组合

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

一个解中可以有重复数字, 但不能有两个相同的解

java

class Solution {

    public List<List<Integer>> combinationSum2(int[] arr, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(arr);
        this.backtrack(res, arr, new ArrayList<>(), 0, target);
        return res;
    }

    private void backtrack(List<List<Integer>> res, int[] arr, List<Integer> list, int start, int target) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            if (target < arr[i]) return;
            // 起始元素只选一次
            if (i > start && arr[i] == arr[i - 1]) continue;
            list.add(arr[i]);
            backtrack(res, arr, list, i + 1, target - arr[i]);
            list.removeLast();
        }
    }
}

77. 组合 mid

给定两个整数 n 和 k，返回区间范围 [1, n] 中所有可能的 k 个数的组合。

java

class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtracking(res, new ArrayDeque<>(), 1, k, n);
        return res;
    }

    private void backtracking(List<List<Integer>> res, Deque<Integer> ele, int start, int cnt, final int n) {
        if (cnt == 0) {
            res.add(new ArrayList<>(ele));
            return;
        }
        // 从 [i, n] 中要有 cnt 个, 所以 max(i) 满足: n-(i)+1 == cnt, 即 i = n-cnt+1
        for (int i = start; i <= n - cnt + 1; i++) {
            ele.add(i);
            backtracking(res, ele, i + 1, cnt - 1, n);
            ele.removeLast();
        }
    }
}

216. 组合总和 III mid

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字 1 到 9
每个数字最多使用一次

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

java

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> elements = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(k, 1, n);
        return res;
    }

    // k 几个数倒数
    // start 递归中的起始位
    // target 递归中的目标值
    private void backtrack(int k, int start, int target) {
        if (target < 0) return;
        if (k == 0 && target == 0) {
            res.add(new ArrayList<>(elements));
            return;
        }
        for (int i = start; i < 10; i++) {
            elements.add(i);
            backtrack(k - 1, i + 1, target - i);
            elements.remove(elements.size() - 1);
        }
    }
}

241. 为运算表达式设计优先级 mid

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。 expression 由数字和算符 '+'、'-' 和 '*' 组成。

如果只有数字, 返回数字; 如果有操作符, 左右递归结果的笛卡尔积

Java

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                // 笛卡尔积
                for (int l : left) {
                    for (int r : right) {
                        switch (c) {
                            case '+':
                                res.add(l + r);
                                break;

                            case '-':
                                res.add(l - r);
                                break;

                            case '*':
                                res.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        // 只有数字
        if (res.size() == 0) res.add(Integer.valueOf(expression));
        return res;
    }
}

784. 字母大小写全排列 mid

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回所有可能得到的字符串集合。以任意顺序返回输出。

解法回溯

java

class Solution {
    private List<String> res = new ArrayList<>();
    private StringBuilder sb;

    public List<String> letterCasePermutation(String s) {
        sb = new StringBuilder(s);
        backtrace(0);
        return res;
    }

    private void backtrace(int i) {
        if (i == sb.length()) {
            res.add(sb.toString());
            return;
        }
        char c = sb.charAt(i);
        backtrace(i + 1);
        if (c >= 'A') {
            sb.setCharAt(i, (char) (c ^ 32));
            backtrace(i + 1);
        }
    }
}

还有一种 bitmap 掩码的方法, 可以看题解

全排列

46. 全排列 mid

剑指 Offer II 083. 没有重复元素集合的全排列

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

通过交换元素位置进行回溯时间复杂度: 每次递归 $n!$ 进行 $n$ 次递归; $O (n) = n * n!$

java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        Integer[] arr = IntStream.of(nums).boxed().toArray(Integer[]::new);
        backtrack(arr, 0);
        return res;
    }

    private void backtrack(Integer[] arr, int start) {
        if (start == arr.length) {
            res.add(List.of(arr));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i);
            backtrack(arr, start + 1);
            swap(arr, start, i);
        }
    }

    private void swap(Integer[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

47. 全排列 II mid

给定一个可包含重复数字的序列 nums，按任意顺序返回所有不重复的全排列。

解法 1 交换法

交换法在交换过程中会乱序, 排序然后比较前一个的去重不适用

java

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Integer[] arr = IntStream.of(nums).boxed().toArray(Integer[]::new);
        backtrack(arr, 0);
        return res;
    }

    private void backtrack(Integer[] arr, int start) {
        if (arr.length == start) {
            res.add(List.of(arr));
            return;
        }
        // 同一层次选择列表中只选一次
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < arr.length; i++) {
            if (set.contains(arr[i])) continue;
            set.add(arr[i]);
            swap(arr, i, start);
            backtrack(arr, start + 1);
            swap(arr, i, start);
        }
    }

    private void swap(Integer[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

解法 2 枚举法

每个位置都从剩余列表里面遍历, 需要先排序; 记录前一个相同元素有没有被选择, 选择了才能选这一个

java

class Solution {
    private boolean[] visit;
    private int[] nums;
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        visit = new boolean[nums.length];
        this.nums = nums;
        Arrays.sort(this.nums);
        backtrace(0, new Integer[nums.length]);
        return res;
    }

    private void backtrace(int idx, Integer[] output) {
        if (idx == nums.length) {
            res.add(List.of(output));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visit[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1]) continue;
            output[idx] = nums[i];
            visit[i] = true;
            backtrace(idx + 1, output);
            visit[i] = false;
        }
    }
}

全部子集

78. 子集 mid

给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> ele = new ArrayList<>();
        res.add(ele);// 空集
        for (int i = 1; i <= nums.length; i++) {
            ele.clear();
            backtrack(res, ele, nums, 0, i);
        }
        return res;
    }

    private void backtrack(List<List<Integer>> res, List<Integer> ele, int[] nums, int idx, int cnt) {
        if (cnt == 0) {
            res.add(new ArrayList<>(ele));
            return;
        }
        // 从 [i, n-1] 中要有 cnt 个, 所以 max(i) 满足: n-1-(i)+1 == cnt, 即 i = n-cnt
        for (int i = idx; i <= nums.length - cnt; i++) {
            ele.add(nums[i]);
            backtrack(res, ele, nums, i + 1, cnt - 1);
            ele.removeLast();
        }
    }
}

90. 子集 II mid

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

不包含重复的意思是, 重复数量不同可以算不同子集, 重复数量相同不行

解法 1 递归中循环

java

class Solution {

    boolean[] visit;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> ele = new ArrayList<>();
        res.add(ele);
        Arrays.sort(nums);
        visit = new boolean[nums.length];
        for (int i = 1; i <= nums.length; i++) {
            ele.clear();
            backtrack(res, ele, nums, 0, i);
        }
        return res;
    }

    private void backtrack(List<List<Integer>> res, List<Integer> ele, int[] nums, int idx, int cnt) {
        if (cnt == 0) {
            res.add(new ArrayList<>(ele));
            return;
        }
        // 从 [i, n-1] 中要有 cnt 个, 所以 max(i) 满足: n-1-(i)+1 == cnt, 即 i = n-cnt
        for (int i = idx; i < nums.length + 1 - cnt; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1]) continue;
            ele.add(nums[i]);
            visit[i] = true;
            backtrack(res, ele, nums, i + 1, cnt - 1);
            visit[i] = false;
            ele.removeLast();
        }
    }
}

解法 2 递归中分类

java

class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<Integer> ele = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        dfs(res, ele, 0, nums);
        return res;
    }

    public void dfs(List<List<Integer>> res, List<Integer> ele, int i, int[] nums) {
        if (i == nums.length) {
            res.add(new ArrayList<>(ele));
            return;
        }
        ele.add(nums[i]);
        dfs(res, ele, i + 1, nums);
        ele.removeLast();

        // 不选就跳过后面一样的数
        while (i + 1 < nums.length && nums[i + 1] == nums[i]) i++;
        dfs(res, ele, i + 1, nums);

    }
}

分割

93. 复原 IP 地址 mid

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

用 '.' 分隔, 终止条件 cnt('.')=3

解法 1: 分隔

java

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        backtrack(res, s, new StringBuilder(), 3, 0);
        return res;
    }

    /**
     * 一部分指向原字符串s, 一部分处理新字符串sb
     *
     * @param cnt   '.'剩余数量
     * @param start 一段的起始位置
     */
    private void backtrack(List<String> res, String s, StringBuilder sb, int cnt, int start) {
        if (cnt == 0) {
            String tail = s.substring(start);
            if (valid(tail)) res.add(sb.append(tail).toString());
            return;
        }
        // i:子段的长度
        for (int i = 1; i <= 3 && start + i <= s.length(); i++) {
            String sub = s.substring(start, start + i);
            if (!valid(sub)) continue;
            int sbStart = sb.length();
            sb.append(sub).append(".");
            backtrack(res, s, sb, cnt - 1, start + i);
            sb.delete(sbStart, sb.length());
        }
    }

    private boolean valid(String s) {
        int n = s.length();
        if (n == 0 || n > 3) return false;
        int num = Integer.parseInt(s);
        return switch (n) {
            case 1 -> true;
            case 2 -> num >= 10;
            case 3 -> num >= 100 && num <= 255;
            default -> false;
        };
    }
}

131. 分割回文串 mid

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

回文串是正着读和反着读都一样的字符串。

预处理判断 [i,j] 能不能分割
从头到尾, 循环尝试分割, 递归分割下一个字串

java

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> ele = new ArrayList<>();
    boolean[][] f;

    public List<List<String>> partition(String s) {
        int n = s.length();
        f = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                boolean equal = s.charAt(i) == s.charAt(j);
                if (j - i == 1) f[i][j] = equal;
                else f[i][j] = equal && f[i + 1][j - 1];
            }
        }
        backtrack(0, s);
        return res;
    }

    private void backtrack(int start, String s) {
        if (start == s.length()) {
            res.add(new ArrayList<>(ele));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (f[start][i]) {
                ele.add(s.substring(start, i + 1));
                backtrack(i + 1, s);
                ele.removeLast();
            }
        }
    }
}

140. 单词拆分 II hard

给定一个字符串 s 和一个字符串字典 wordDict，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

解法 DFS

匹配到第 1 个后递归下一个
剪枝, 需要记忆化不可行的路线
substring 太慢, startWith 快

java

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<>();
        boolean[] memo = new boolean[s.length() + 1];
        Arrays.fill(memo, true); // 乐观
        dfs(s, wordDict, new ArrayList<>(), res, 0, memo);
        return res;
    }

    private boolean dfs(String s, List<String> wordDict,
                        List<String> list, List<String> res,
                        int start, boolean[] memo) {
        if (start == s.length()) {
            StringBuilder sb = new StringBuilder();
            for (String e : list) {
                sb.append(e).append(' ');
            }
            res.add(sb.toString().trim());
            return true;
        }
        if (!memo[start]) return memo[start];
        boolean ok = false;
        for (String word : wordDict) {
            if (s.startsWith(word, start)) {
                list.add(word);
                if (dfs(s, wordDict, list, res, start + word.length(), memo)) ok = true;
                list.removeLast();
            }
        }
        memo[start] = ok;
        return ok;
    }
}

所有路径

257. 二叉树的所有路径 easy

给你一个二叉树的根节点 root，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]

java

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        backtracking(res, new StringBuilder(), root);
        return res;
    }

    private void backtracking(List<String> res, StringBuilder sb, TreeNode n) {
        int len = sb.length();
        if (!sb.isEmpty()) {
            sb.append("->");
        }
        sb.append(n.val);
        if (n.left == null && n.right == null) {
            res.add(sb.toString());
            return;
        }
        if (n.left != null) {
            int len1 = sb.length();
            backtracking(res, sb, n.left);
            sb.delete(len1, sb.length());
        }
        if (n.right != null) {
            backtracking(res, sb, n.right);
        }
        sb.delete(len, sb.length());
    }
}

组合是否成立

基本上就是回溯处理, 有时候递归

37. 解数独 hard

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.'表示。

解数独最快的是舞蹈链算法; 回溯可以用状态压缩;
回溯可以用递归

java

class Solution {
    public void solveSudoku(char[][] board) {
        this.solveSudokuHelper(board);
    }

    private boolean solveSudokuHelper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') continue;
                for (char k = '1'; k <= '9'; k++) {
                    // 每个位置都拿 0-9 试一试
                    if (this.isValidSudoku(i, j, k, board)) {
                        board[i][j] = k;
                        // 递归
                        if (this.solveSudokuHelper(board)) return true;
                        board[i][j] = '.';
                    }
                }
                // 填不了
                return false;
            }
        }
        // 填满了
        return true;
    }

    private boolean isValidSudoku(int row, int col, char val, char[][] board) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == val) return false;
        }
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == val) return false;
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val) return false;
            }
        }
        return true;
    }
}

301. 删除无效的括号 hard

给你一个由若干括号和字母组成的字符串 s，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按任意顺序返回。

不能直接用栈做, 有删除操作, 匹配过程不是唯一的. 例如: "()())"

解法 1 回溯

先分别统计需要删减的左右括号数量, 根据这 2 个数量尝试回溯删除

java

class Solution {
    private final List<String> res = new ArrayList<>();

    public List<String> removeInvalidParentheses(String s) {
        int lcnt = 0;
        int rcnt = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') lcnt++;
            else if (s.charAt(i) == ')') {
                if (lcnt == 0) rcnt++;
                else lcnt--;
            }
        }
        backtracking(new StringBuilder(s), 0, lcnt, rcnt);
        return res;
    }

    /**
     * @param start 从哪开始删
     * @param lcnt  '(' 要删除的数量
     * @param rcnt  ')' 要删除的数量
     */
    private void backtracking(StringBuilder s, int start, int lcnt, int rcnt) {

        if (lcnt == 0 && rcnt == 0) {
            if (isValid(s)) res.add(s.toString());
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (s.charAt(i) != ')' && s.charAt(i) != '(') continue;
            // 不能删除 剪枝
            if (lcnt + rcnt > s.length() - i) return;
            // 重复的跳过
            if (i > start && s.charAt(i) == s.charAt(i - 1)) continue;
            // 尝试删除
            if (lcnt > 0 && s.charAt(i) == '(') {
                backtracking(s.deleteCharAt(i), i, lcnt - 1, rcnt);
                s.insert(i, '(');
            } else if (rcnt > 0 && s.charAt(i) == ')') {
                backtracking(s.deleteCharAt(i), i, lcnt, rcnt - 1);
                s.insert(i, ')');
            }
        }
    }

    private boolean isValid(StringBuilder s) {
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') cnt++;
            else if (s.charAt(i) == ')') {
                cnt--;
                if (cnt < 0) return false;
            }
        }
        return cnt == 0;
    }
}

解法 2 BFS

枚举删除每个元素, 删除后的结果作为下一轮

java

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        Set<String> currSet = new HashSet<>();
        currSet.add(s);
        while (!currSet.isEmpty()) {
            for (String str : currSet) {
                if (isValid(str)) res.add(str);
            }
            if (!res.isEmpty()) return res;
            Set<String> nextSet = new HashSet<>();
            for (String str : currSet) {
                for (int i = 0; i < str.length(); i++) {
                    if (str.charAt(i) != '(' && str.charAt(i) != ')' ||
                            i > 0 && str.charAt(i) == str.charAt(i - 1)) continue;
                    nextSet.add(str.substring(0, i) + str.substring(i + 1));
                }
            }
            currSet = nextSet;
        }
        return res;
    }

    private boolean isValid(String s) {
        int cnt = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                cnt++;
            } else if (c == ')') {
                cnt--;
                if (cnt < 0) return false;
            }
        }
        return cnt == 0;
    }
}

组合 ​

组合全集 ​

17. 电话号码的字母组合 mid ​

22. 括号生成 mid ​

39. 组合总和 mid ​

40. 组合总和 II mid ​

77. 组合 mid ​

216. 组合总和 III mid ​

241. 为运算表达式设计优先级 mid ​

784. 字母大小写全排列 mid ​

全排列 ​

46. 全排列 mid ​

47. 全排列 II mid ​

全部子集 ​

78. 子集 mid ​

90. 子集 II mid ​

分割 ​

93. 复原 IP 地址 mid ​

131. 分割回文串 mid ​

140. 单词拆分 II hard ​

所有路径 ​

257. 二叉树的所有路径 easy ​

组合是否成立 ​

37. 解数独 hard ​

301. 删除无效的括号 hard ​

组合

组合全集

17. 电话号码的字母组合 mid

22. 括号生成 mid

39. 组合总和 mid

40. 组合总和 II mid

77. 组合 mid

216. 组合总和 III mid

241. 为运算表达式设计优先级 mid

784. 字母大小写全排列 mid

全排列

46. 全排列 mid

47. 全排列 II mid

全部子集

78. 子集 mid

90. 子集 II mid

分割

93. 复原 IP 地址 mid

131. 分割回文串 mid

140. 单词拆分 II hard

所有路径

257. 二叉树的所有路径 easy

组合是否成立

37. 解数独 hard

301. 删除无效的括号 hard