Day 20 回溯法part02| LeetCode 39. 组合总和 ，40.组合总和II，131.分割回文串

39. 组合总和

39. 组合总和

 class Solution {
        public List<List<Integer>> res = new ArrayList<>();
        public List<Integer> path = new LinkedList<>();

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

        void backtracking(int[] candidates, int target, int startIndex) {
            if (target < 0)
                return;
            if (target == 0) {
                res.add(new ArrayList<>(path));
                return;
            }
            //单层搜索

            for (int i = startIndex; i < candidates.length ; i++) {

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

        }


    }

剪枝

 class Solution {
        public List<List<Integer>> res = new ArrayList<>();
        public List<Integer> path = new LinkedList<>();

        public List<List<Integer>> combinationSum(int[] candidates, int target) {

            //排序
            Arrays.sort(candidates);
            backtracking(candidates, target, 0);
            return res;
        }

        void backtracking(int[] candidates, int target, int startIndex) {
            if (target < 0)
                return;
            if (target == 0) {
                res.add(new ArrayList<>(path));
                return;
            }
            //单层搜索

            for (int i = startIndex; i < candidates.length ; i++) {

                //剪枝优化
                if(target<0) break;
                path.add(candidates[i]);
                //target -= candidates[i];
              
                backtracking(candidates, target - candidates[i],i );
                int size = path.size();
                path.remove(size - 1);
                // target += candidates[i];
            }

        }


    }

40.组合总和II

40. 组合总和 II

class Solution {
        public  List<Integer> path=new LinkedList<>();
        public  List<List<Integer>> res=new ArrayList<>();


        public List<List<Integer>> combinationSum2(int[] candidates, int target) {

            int l=candidates.length;
//            boolean [] used=new boolean[][l];
            Arrays.sort(candidates);
            backtracking(candidates,target,0);
            return res;
        }
        void backtracking(int[] candidates, int target,int startIndex)
        {

            if(target<0)return;
            if(target==0)
            {
                res.add(new ArrayList<>(path));
                return;
            }
            for(int i=startIndex;i<candidates.length;i++)
            {
                //去重，不使用used数组
                if(i>startIndex&& candidates[i]==candidates[i-1]) continue;

                //剪枝
                if(target<0) break;
                path.add(candidates[i]);
                backtracking(candidates,target-candidates[i],i+1);
               int size=path.size();
               path.remove(size-1);
            }
        }
    }

131.分割回文串

131. 分割回文串

  class Solution {
        List<List<String>> res=new ArrayList<>();
        List<String> path=new LinkedList<>();
        public List<List<String>> partition(String s) {

            backtracking(s,0,new StringBuilder());
            return res;
        }
        void backtracking(String s,int startIndex,StringBuilder b)
        {
            if(startIndex==s.length())
            {
                res.add(new ArrayList<>(path));
                return ;
            }


            for(int i=startIndex;i<s.length();i++)
            {
                b.append(s.charAt(i));
                if(isPalindrome(b))
                {
                        path.add(b.toString());
                        backtracking(s,i+1,new StringBuilder());
                        path.remove(path.size()-1);
                }
            }
        }

        boolean isPalindrome(StringBuilder b)
        {

            for(int i=0,j=b.length()-1;i<j;i++,j--)
            {
                if(b.charAt(i)!=b.charAt(j))
                    return false;
            }
            return true;
        }
    }