几个回溯法的解题思路方法

Contents

1. 1. 介绍
2. 2. Permutation (不重复元素的数组全排列)
3. 3. pathSum II
4. 4. Subset
5. 5. Combination Sum
6. 6. Combination Sum II

介绍

回溯就是让计算机自动的去搜索，碰到符合的情况就结束或者保存起来，在一条路径上走到尽头也不能找出解，就回到原来的岔路口，选择一条以前没有走过的路继续探测，直到找到解或者走完所有路径为止。

Permutation (不重复元素的数组全排列)

题目：
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 static List<List<Integer>> permute(int[] nums){
	List<List<Integer>> res = new ArrayList<List<Integer>>();
	helper(nums,0,res);
	return res;

}
/*递归
 * **/
public static void helper(int nums[],int start,List<List<Integer>> res ){
	//递归结束条件
	if(start>= nums.length){
		res.add(array2List(nums));
	}
	for(int i=start;i<nums.length;i++){
		swap(start,i,nums);
		helper(nums,start+1,res);
		swap(start,i,nums);
	}
}
/*
 * 交换
 * **/
public static void swap(int i, int j, int[] a){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}
/*
 * 数组变成list（基本类型的数组不能用Arrays.toList）
 * **/
public static List<Integer> array2List(int[] nums){
	List<Integer> list = new ArrayList<Integer>();
	for(int i:nums)list.add(i);//这里是自动装箱了，int自动变成Integer
	return list;
}

具体的递归过程可以用下图表示：

pathSum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1
return
[
[5,4,11,2],
[5,8,4,5]
]

思路：从根节点出发，分别往左右儿子探索，到达叶节点时候看是否满足sum要求，满足则添加至结果列表中，否则递归跳出，删掉上一个节点，继续往别的方向探索可能性。

代码：

public  List<List<Integer>> pathSum(TreeNode root, int sum) {
	List<List<Integer>> res = new ArrayList<List<Integer>>();
	List<Integer> list = new ArrayList<Integer>();
	if(root == null) return res;
	helper(res,list,root,sum);
	return res;	
		
}
public  void helper(List<List<Integer>> res, List<Integer> list, TreeNode root,int sum){
	//递归停止条件
	if(root==null) return;
	
	list.add(root.val);
	//访问到叶节点了
	if(root.left == null && root.right == null && root.val == sum){
		res.add(new ArrayList<Integer>(list));
	}else{
    	//不是叶节点
    	helper(res, list, root.left,sum-root.val);
    	helper(res, list, root.right,sum-root.val);
	}
	//返回上一层之前把这一层最后一个数删掉
	list.remove(list.size()-1);

}

Subset

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],
  []
]

//思路，递归的回溯法解决
//i从0到n-1 每次加每次从i开始依次添加后面的元素
   public static List<List<Integer>> subsets(int[] nums) {
   	List<List<Integer>> res = new ArrayList<List<Integer>>();
   	backtrack(nums,res,new ArrayList<Integer>(),0);
	return res;
   	
   }
   public static void backtrack(int[] nums, List<List<Integer>> res, List<Integer> list ,int start){
   	//递归结束条件
   	res.add(new ArrayList<Integer>(list));//必须重新拷贝一个
   	for(int i=start;i<nums.length;i++){
   		list.add(nums[i]);
   		backtrack(nums,res,list,i+1);
   		list.remove(list.size()-1);//把出栈前的最后一个元素删掉
   	}
   }

Combination Sum

Given a set of candidate numbers (C) 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:

[
    [7],
    [2, 2, 3]
]

/*
 * 思路：用递归的回溯法，考虑元素的所有可能的组合，但是得考虑重复，类似于subsetII
 * **/
   public static List<List<Integer>> combinationSum(int[] candidates, int target) {
   	List<List<Integer>> res = new ArrayList<List<Integer>>();
   	Arrays.sort(candidates);
   	backtrack(candidates,target,res,new ArrayList<Integer>(), 0);
   	
	return res;
       
   }
   public static void backtrack(int[] nums,int target, List<List<Integer>> res,List<Integer> list, int start) {
   	
   		if(target<0) return;
   		else if(target == 0){
   			res.add(new ArrayList(list));
   		}else{
   			for(int i=start;i<nums.length;i++){
   				list.add(nums[i]);
           		backtrack(nums,target-nums[i],res,list,i);//不是i+1是因为可以有重复的元素
           		list.remove(list.size()-1);
   			}
   			
   		}
       	
   	}

Combination Sum II

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 static List<List<Integer>> combinationSum2(int[] nums, int target) {

  	List<List<Integer>> res = new ArrayList<List<Integer>>();
  	Arrays.sort(nums);
  	backtrack(nums,target,res,new ArrayList<Integer>(), 0);
  	
return res;
      
  }
  public static void backtrack(int[] nums,int remain, List<List<Integer>> res,List<Integer> list, int start) {
  	if(remain<0) return;
  	else if(remain == 0){
  		res.add(new ArrayList<Integer>(list));
  	}else{
  		for(int i=start;i<nums.length;i++){
  			//筛掉重复的
  			if(i>start && nums[i]==nums[i-1])continue;
  			list.add(nums[i]);
  			backtrack(nums,remain-nums[i],res,list,i+1);
  			list.remove(list.size()-1);
  		}
  	}
  
  }