代码随想录算法训练营第二十六天

LeetCode 39.组合总和

和216组合总和iii有相似之处，唯一的区别就是给定了candidates数组以及允许数字重复使用，只需要稍微调整一下下层递归的起始index即可。

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();

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

    private void backtracking (int target, int[] candidates, int startIndex) {

        // if target is less than 0, exits
        if (target < 0) {
            return;
            // if find a successful combo, add it into ans
        }else if (target == 0) {
            List<Integer> combo = new LinkedList<>();
            combo.addAll(path);
            ans.add(combo);
        }


        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);

            // note here, by seting the startIndex to i , it means that
            // the next element can still start with candidates[i]
            // this allows path like [2,2,3]
            // but at the mean time, it prevents the path like [3,2,2]
            // and through this way it removes some duplicates path
            backtracking(target - candidates[i], candidates, i);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 40 组合总和ii

这道题的核心在于去重，注意我们的目的是同层遍历去重，所以通过检验当前元素是否是在同层上与左侧元素相同即可。

(转载自代码随想录)

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);

        backtracking(candidates, target, 0);

        return ans;
    }

    private void backtracking(int[] candidates, int target, int index) {

        if (target < 0) {
            return;
            // if find a successful combo, add it into ans
        }else if (target == 0) {
            List<Integer> combo = new LinkedList<>();
            combo.addAll(path);
            ans.add(combo);
        }

        for (int i = index; i < candidates.length; i++) {
						
            // we need to avoid the duplicates in the same level for instance, 
          	// if we are chooseing the first num and the candidates is [1, 1, 1, 2]
          	// then the second 1 would result in duplicates
            // this num is same as its left one && they are in the same level
            // then skip it
            if (i > index && candidates[i] == candidates[i - 1]){
                continue;
            }

            path.add(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 131.分割回文串

切割问题，和组合问题有异曲同工之妙，但是稍微有点难想，主要是对分割字符串的操作不是很熟悉。

class Solution {

    private List<List<String>> ans = new LinkedList<>();
    private List<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return ans;

    }

    // for any String such as "aabbccd"
    // start with "a" then "aa", then "aab" 
    private void backtracking (String s, int startIndex) {

        // if we succeed to split the whole string, return
        if (startIndex >= s.length()) {
              List<String> combo = new LinkedList<>();
              combo.addAll(path);
              ans.add(combo);
              return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            
            if (isPalindrome(s, startIndex, i)) {
                path.add(s.substring(startIndex, i + 1));
            }else {
                continue;
            }

            backtracking(s, i + 1);
            path.remove(path.size() - 1);
            
        }

    }

    // test if a sub string is palindrome from startIndex to the endIndex
    private boolean isPalindrome (String s, int startIndex, int endIndex) {
        int i = startIndex;
        int j = endIndex;

        boolean ans = true;

        while ( i <= j) {
            if (s.charAt(i) == s.charAt(j)){
                i++;
                j--;
            }else {
                ans = false;
                break;
            }
        }

        return ans;
    }
}