当前位置：首页 > article >正文

【代码随想录Day27】

article 2025/1/7 18:37:27

Day 27 回溯算法03

今日任务

1. 组合总和
40.组合总和II
131.分割回文串

代码实现

组合总和，直接套模板可解

 public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates, target, 0);
        return result;
    }

    void backtracking(int[] candidates, int target, int startIndex) {
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);
            sum+=candidates[i];
            backtracking(candidates, target, i);
            sum-=candidates[i];
            path.remove(path.size() - 1);
        }
    }

组合总和II
这个就有点难，在模板之外要考虑怎么去重

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking2(candidates, target, 0, new boolean[candidates.length]);
        return result;
    }

    void backtracking2(int[] candidates, int target, int startIndex, boolean[] used) {
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (target - sum < candidates[i]) break;
            if ( i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            path.add(candidates[i]);
            sum+=candidates[i];
            backtracking2(candidates, target, i + 1, used);
            used[i] = false;
            sum-=candidates[i];
            path.remove(path.size() - 1);
        }

    }

131.分割回文串
这个就太难了，模板还是那个模板，这里难以想到的是，当切割字符串的时候，从第二位开始，就相当于把第1、2位切割为一个字符，也就是说把startIndex当成切割线；至于解法中的动态规划部分，则完全不懂。

    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        backtracking(s, 0, result, path);
        return result;

    }

    void backtracking(String s, Integer startIndex, List<List<String>> result, List<String> path) {
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            String substring = s.substring(startIndex, i + 1);
            if (!isPalindrome(substring)) {
                continue;
            }
            path.add(substring);
            backtracking(s, i + 1, result, path);
            path.remove(path.size() - 1);
        }

    }

    public boolean isPalindrome(String s) {
        for (int i = 0; i < s.length()/2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }