回溯法

作者: mrjunwang | 来源:发表于2018-08-13 10:10 被阅读0次

N皇后
简单的谈谈dfs
算法08-回溯法：面试最常见问题
回溯法与分支限界法
LeetCode之回溯算法
小朋友学经典算法（14）：回溯法和八皇后问题
算法的设计思想2
算法理论 | 回溯法
78. Subsets
491. Increasing Subsequences

回溯法动态规划题目
https://www.cnblogs.com/jiangchen/p/5930049.html
回溯法概念（http://www.cnblogs.com/jiangchen/p/5393849.html）

LeetCode 39. Combination Sum （组合的和）

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; word-wrap: break-word;">[
[7],
[2, 2, 3]
]</pre>
题目标签：Array

题目给了我们一个candidates array 和一个 target，让我们从array 里找到所有的组合，它的和是等于target的。任何组合只要是它的和等于target的话，都需要找到，但是不需要重复的。这道题中是可以重复利用一个数字的，那么我们就需要每次都代入同一个数字，直到它之和达到target 或者它超过了target，然后在倒退回去一个数字，继续找下一个数字，这种情况肯定是要用递归了。这里是backtracking，每次倒退回一个数字，需要继续递归下去，在倒退，一直重复直到搜索了所有的可能性。

我们可以看原题中的例子：

[2,3,6,7] target 7

2 选2，sum = 2

2+2 选2，sum = 4

2+2+2 选2，sum = 6

2+2+2+2 选2，sum = 8 这时候 sum已经超出target，需要返回到上一个数字

2+2+2+3 选3，sum = 9，也超出了target，这里我们可以发现，如果是sorted array的话，从小到大，只要一次超出，后面的数字必然也会超出target，所以可以在第一次超出的时候就直接跳出这一个迭代

2+2+3 选3，sum = 7，等于target，此时返回并且跳出这一个迭代，因为后面的数字肯定超出（array里不会有重复的数字）

2+3 选3，sum = 5，小于target，继续递归同一个数字

2+3+3 选3，sum = 8，超出target，返回上一个数字

2+6 选6，sum = 8，超出target，返回上一个数字

3 选3，这里继续从3开始递归

...

我们可以看出，一开始有一个迭代从2，一直到7，然后把每一个数字递归下去，包括它自己，每次递归下去的数字，会继续有一个迭代，一旦超出或者等于了，返回前面一个数字继续递归。所以把array sort一下就可以提早跳出那一轮的迭代。
数组中的每个数字可以用多次：

public List<List<Integer>>  getAllCombination(int[] arr,int target){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(arr);
        backTracking(resList,curList,arr,target,0);
        return resList;
    }

    /**
     * @param resList
     * @param curList
     * @param arr
     * @param target
     * @param i
     *<p>Description: </p>  
     */
    private boolean backTracking(List<List<Integer>> resList,
            List<Integer> curList, int[] arr, int remain, int start) {

        if(remain==0){
            resList.add(new ArrayList<Integer>(curList));
            return false;
        }
        if(remain<0){
            return false;
        }
        else{
            for(int i=start;i<arr.length;i++){
                curList.add(arr[i]);
                boolean flag=backTracking(resList, curList, arr, remain-arr[i], i);
                curList.remove(curList.size()-1);
                if(!flag){
                    break;
                }
            }
            return true;

        }
    }

如果数组中不包含重复的元素的，且每个元素只能用一次。

public List<List<Integer>>  getAllCombinationUnduplicate(int[] arr,int target){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(arr);
        backTrackingUnduplicate(resList,curList,arr,target,0);
        return resList;
    }
    private boolean backTrackingUnduplicate(List<List<Integer>> resList,
            List<Integer> curList, int[] arr, int remain, int start) {

        if(remain==0){
            resList.add(new ArrayList<Integer>(curList));
            return false;
        }
        if(remain<0){
            return false;
        }
        else{
            for(int i=start;i<arr.length;i++){
                
                curList.add(arr[i]);
                boolean flag=backTrackingUnduplicate(resList, curList, arr, remain-arr[i], i+1);
                curList.remove(curList.size()-1);
                if(!flag){
                    break;
                }
            }
            return true;

        }
    }

数组中包含有重复的元素，且每个元素只能用一次。最后的结果中不含重复的结果集。
Combination Sum 2

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

public List<List<Integer>>  getAllCombinationUnduplicate(int[] arr,int target){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(arr);
        backTrackingUnduplicate(resList,curList,arr,target,0);
        return resList;
    }
    private boolean backTrackingUnduplicate(List<List<Integer>> resList,
            List<Integer> curList, int[] arr, int remain, int start) {

        if(remain==0){
            resList.add(new ArrayList<Integer>(curList));
            return false;
        }
        if(remain<0){
            return false;
        }
        else{
            for(int i=start;i<arr.length;i++){
                curList.add(arr[i]);
                boolean flag=backTrackingUnduplicate(resList, curList, arr, remain-arr[i], i+1);
                curList.remove(curList.size()-1);
                if(!flag){
                    break;
                }
                while(i<arr.length-1 && arr[i]==arr[i+1]){
                    i++;
                }
            }
            return true;

        }
    }

比如数组a={1,1,1,1,2}，target=4.用上面解法的过程见下图：

image.png

Combination Sum 3

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]
Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

public List<List<Integer>>  getAllCombinationUnduplicate(int[] arr,int target,int k){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(arr);
        int count=0;
        backTrackingUnduplicate(resList,curList,arr,target,0,k);
        return resList;
    }
    private boolean backTrackingUnduplicate(List<List<Integer>> resList,
            List<Integer> curList, int[] arr, int remain, int start,int k) {

        if(remain==0 && curList.size()==k){
            
            resList.add(new ArrayList<Integer>(curList));
            return false;
        }
        if(remain<0){
            return false;
        }
        else{
            for(int i=start;i<arr.length;i++){
                if(remain-arr[i]>0 && curList.size()+1==k ){
                    continue;
                }
                curList.add(arr[i]);
                boolean flag=backTrackingUnduplicate(resList, curList, arr, remain-arr[i], i+1,k);
                curList.remove(curList.size()-1);
                if(!flag){
                    break;
                }
                while(i<arr.length-1 && arr[i]==arr[i+1]){
                    i++;
                }
            }
            return true;

        }
    }

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

    public List<List<Integer>> getAllCombinations(int[] a,int k){
        List<List<Integer>> resList = new ArrayList<>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(a);
        backTrack(resList, curList, a, 0,k);
        return resList;
    }
    /**
     * @param resList
     * @param curList
     * @param a
     * @param i
     *<p>Description: </p>  
     */
    private void backTrack(List<List<Integer>> resList,
            List<Integer> curList, int[] a, int start,int k) {
        if(curList.size()==k){
            resList.add(new ArrayList(curList));
            return;
        }
        
        for(int i=start;i<a.length;i++){
            curList.add(a[i]);
            backTrack(resList, curList, a, i+1, k);
            curList.remove(curList.size()-1);
        }
        //return;写不写的区别是啥
        
    }

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

image.png

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

public List<String> getStringCombinaList(String input){
        List<String> resList=new ArrayList<>();
        StringBuilder sb=new StringBuilder();
        Map<Character,String> map=new HashMap();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put ('5', "jkl");
        map.put ('6', "mno");
        map.put ('7', "pqrs");
        map.put ('8', "tuv");
        map.put ('9', "wxyz");
        int start=0;
        backTrackHelper(resList,sb,input,map,start);
        return resList;
        
        
        
    }
    /**
     * @param resList
     * @param sb
     * @param input
     * @param map
     * @param start
     *<p>Description: </p>  
     */
    private void backTrackHelper(List<String> resList, StringBuilder sb,
            String input, Map<Character, String> map, int start) {

        if(sb.length()==input.length()){
            resList.add(sb.toString());
            return;
        }
        String temp=map.get(input.charAt(start));
        for(int i=0;i<temp.length();i++){
            sb.append(temp.charAt(i));
            backTrackHelper(resList, sb, input, map, start+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解法1：回溯

public List<List<Integer>> getAllSet(List list){
       List<List<Integer>> resList=new ArrayList();
       if(list.size()==0){
           return resList;
       }
       List curList=new ArrayList<>();
       backTrackSubset(resList,list,curList,0);
       return resList;
   }

   /**
    * @param resList
    * @param list
    * @param i
    *<p>Description: </p>  
    */
   private void backTrackSubset(List<List<Integer>> resList, List list,List curList, int current) {

       resList.add(new ArrayList(curList));
       
       for(int i=current;i<list.size();i++){
           curList.add(list.get(i));
           backTrackSubset(resList, list, curList, i+1);
           curList.remove(curList.size()-1);
       }
   }

解法2：动态规划（有个问题没有解决）
Java集合的拷贝构造函数只提供浅拷贝而不是深拷贝

public Set<Set<Integer>> getAllSubSetDyn(int[] a,int n){
        Set<Set<Integer>> resSet=new HashSet<>();
        if(n==0){
        resSet.add(new HashSet<>());
        return resSet;
        }
        Set<Set<Integer>> set=getAllSubSetDyn(a, n-1);
        for(Set<Integer> s:set){
            Set<Integer> setCopy=new HashSet<>(s);//集合默认是浅拷贝
            setCopy.add(a[n-1]);
            resSet.add(new HashSet<Integer>(setCopy));//    resSet.add(setCopy);

            resSet.add(new HashSet<Integer>(s));
        }
        return resSet;
    }

Subsets II (contains duplicates)

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

public List<List<Integer>> getAllSetDuplicate(int[] a){
       List<List<Integer>> resList=new ArrayList<>();

       if(a.length<=0){
           return resList;
       }
       Arrays.sort(a);
       List curList=new ArrayList<>();
       backTrackSubsetDuplicate(resList,curList,a,0);
       return resList;
       
   }
   /**
    * @param resList
    * @param curList
    * @param a
    * @param i
    *<p>Description: </p>  
    */
   private void backTrackSubsetDuplicate(List<List<Integer>> resList,
           List curList, int[] a, int start) {

       resList.add(new ArrayList<>(curList));
       for(int i=start;i<a.length;i++){
           curList.add(a[i]);
           backTrackSubsetDuplicate(resList, curList, a, i+1);
           curList.remove(curList.size()-1);
           while(i<a.length-1 && a[i]==a[i+1]){
               i++;
           }
       }
   }

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

public List<List<Integer>> getPermutations(int[] a){
        List<List<Integer>> resList=new ArrayList<>();
        if(a.length<=0){
            return resList;
        }
        
        List<Integer> curList=new ArrayList<>();
        backtrackPermutation(resList,curList,a);
        return resList;
    }
    /**
     * @param resList
     * @param curList
     * @param a
     *<p>Description: </p>  
     */
    private void backtrackPermutation(List<List<Integer>> resList,
            List<Integer> curList, int[] a) {

        if(curList.size()==a.length){
            resList.add(new ArrayList<>(curList));
        }
        
        for(int i=0;i<a.length;i++){
            if(curList.contains(a[i])){
                continue;
            }
            curList.add(a[i]);
            backtrackPermutation(resList, curList, a);
            curList.remove(curList.size()-1);
        }
    }

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
[1,1,2],
[1,2,1],
[2,1,1]
]

    
    public List<List<Integer>> getPermutationDuplicate(int a[]){
        List<List<Integer>> resList=new ArrayList<>();
        Arrays.sort(a);
        List<Integer> curList=new ArrayList<>();
        boolean[] flag=new boolean[a.length];
        backTrackPermutationDup(resList,curList,a,flag);
        return resList;
    }

    /**
     * @param resList
     * @param curList
     * @param a
     *<p>Description: </p>  
     */
    private void backTrackPermutationDup(List<List<Integer>> resList,
            List<Integer> curList, int[] a,boolean[] flag) {

        if(curList.size()==a.length){
            resList.add(new ArrayList<Integer>(curList));
        }
        
        
        for(int i=0;i<a.length;i++){
            if(flag[i]){
                continue;
            }
            
            curList.add(a[i]);
            flag[i]=true;
            
            backTrackPermutationDup(resList, curList, a, flag);
            curList.remove(curList.size()-1);
            flag[i]=false;
            while(i<a.length-1 && a[i]==a[i+1]){
                i++;
            }
        }
    }

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

1
/
2 3

5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

public List<String> getAllPaths(TreeNode root){
        List<String> list=new ArrayList<String>();
        if(root == null){
            return list;
        }
        StringBuilder sb=new StringBuilder();
        backTracking(root,list,sb);
        return list;
        
    }
    /**
     * @param root
     * @param list
     * @param sb
     *<p>Description: </p>  
     */
    private void backTracking(TreeNode root, List<String> list, StringBuilder sb) {

        if(root == null){
            return;
        }
        int length=sb.length();

        if(root.getLeft() == null && root.getRight() == null){
            sb.append(root.getValue());
            list.add(sb.toString());
        }
        else{
            sb.append(root.getValue());
            sb.append("->");
            backTracking(root.getLeft(), list, sb);
            backTracking(root.getRight(), list, sb);
        }
    
        sb.setLength(length);//截取
    }

N皇后
回溯法核心代码： n皇后问题回溯法
简单的谈谈dfs
简单的说回溯法，递归就是将函数负责几遍。那么回溯法就是将for循环复制几遍。回溯法框架为什么要把list的最后一...
算法08-回溯法：面试最常见问题
算法08-回溯法：面试最常见问题一、介绍回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜...
回溯法与分支限界法
回溯法与分支限界法时间 2016-03-24 标签搜索回溯法 1、概念回溯算法实际上一个类似枚举的搜索尝...
LeetCode之回溯算法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。因为回溯的本质是穷举，穷...
小朋友学经典算法（14）：回溯法和八皇后问题
一、回溯法回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步...
算法的设计思想2
4，回溯法回溯法是一种优化的穷举法。所谓穷举法就是穷举问题的所有可能性，直到发现解决问题的最佳解为止。回溯法会有...
算法理论 | 回溯法
回溯法回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并...
78. Subsets
经典的回溯法
491. Increasing Subsequences
典型的回溯法