回溯法动态规划题目
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.用上面解法的过程见下图：
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.
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);//截取
}
