LeetCode Day20 BackTracking Part 2

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

Original Page

The difference between this question and the questions solved yesterday is not quite large.


The BackTracking still work well for searching the possibility of depth and using a loop for the width control.


The part that needs attention is that here we can add the same elements and then keep the whole combination unique.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> combs = new LinkedList<>();
        backTracking(list, combs, candidates, target, 0, 0);
        return list;
    }

    public void backTracking(List<List<Integer>>list, List<Integer> combs, int[] candidates, int target, int sum, int start){
        if(sum > target){
            return;
        }
        if(sum == target){
            list.add(new ArrayList<>(combs));
            return;
        }

        for(int i=start; i<candidates.length; i++){
            combs.add(candidates[i]);
            sum += candidates[i];
            backTracking(list, combs, candidates, target, sum, i);
            combs.remove(combs.size()-1);
            sum -= candidates[i];
        }

40. Combination Sum II

Time Limit Exceeded

    Set<List<Integer>> set = new HashSet<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> combs = new LinkedList<>();
        Arrays.sort(candidates);
        backTracking(combs, target, candidates, 0, 0);

        return new ArrayList<>(set);
    }

    public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum){
        if(sum > target){
            return;
        }
        if(sum == target){
            set.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > target){
                continue;
            }

            sum += candidates[i];
            combs.add(candidates[i]);
            backTracking(combs, target, candidates, i+1, sum);
            sum -= candidates[i];
            combs.remove(combs.size()-1);

        }
    }

Because there are some elements that have been used previously e.g. [1,1,1,2,3] 112 has been used in the first recursion but the loop will traverse all elements that starts from 1 to 3 and there are three '1', so when it comes to second '1', the combination 112 will also found, which has been found in previous recursion steps, so we should cut these redundant steps down (similarly it may happen in the recursion's traverse and recursion's recursion's transverse as well.

Fix the problem

    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> combs = new LinkedList<>();
        Arrays.sort(candidates);
        backTracking(combs, target, candidates, 0, 0, false);

        return list;
    }

    public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum, boolean horizon){
        if(sum > target){
            return;
        }
        if(sum == target){
            list.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > target){
                continue;
            }

            if(i!=0 && candidates[i] == candidates[i-1] && horizon){
                continue;
            }

            sum += candidates[i];
            combs.add(candidates[i]);
            backTracking(combs, target, candidates, i+1, sum, false);
            sum -= candidates[i];
            combs.remove(combs.size()-1);
            horizon = true;
        }
    }

131. Palindrome Partitioning

Given a string s, partition s such that every
substring
of the partition is a
palindrome
. Return all possible palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

1 <= s.length <= 16
s contains only lowercase English letters.
Original Page

    List<List<String>> list = new ArrayList<>();
    public List<List<String>> partition(String s) {
        List<String> combs = new ArrayList<>();

        backTracking(combs, new StringBuilder(s), 0);
        return list;
    }

    public void backTracking(List<String> combs, StringBuilder str, int start){
        if(start == str.length()){
            list.add(new ArrayList<>(combs));
            return;
        }

        for(int i=1; i+start <= str.length(); i++){

            String cur = str.substring(start, start+i);

            if(!isParlindrome(cur)){
                continue; 
            } 

            combs.add(cur);
            backTracking(combs, str, start+i);
            combs.remove(combs.size()-1);
        }

    }

    public boolean isParlindrome(String s){
        int left = 0;
        int right = s.length()-1;

        while(left<right){
            if(s.charAt(left++)!=s.charAt(right--)){
                return false;
            }
        }
        return true;
    }