Fork me on GitHub

回溯算法

发表于 | 更新于 | 分类于

基本概念

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。

但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

例题：全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解决方案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    ArrayList list = new ArrayList<Integer>();
    permute(res,list,nums,0);
    return res;
}
public void permute(List<List<Integer>> res,ArrayList<Integer> list,int []nums,int index) {
    if(index == nums.length){
        ArrayList perList = new ArrayList<>();
        perList.addAll(list);
        res.add(perList);
        return;
    }else{
        for(int i = 0;i < nums.length;i++){
            if(!list.contains(nums[i])){
                list.add(nums[i]);
                permute(res,list,nums,index+1);
                list.remove(list.size() - 1);
            }
        }           
    }
}
}