回溯算法

发布： 分类： 评论： 阅读：

回溯法：实现某个元素选或不选的问题。

回溯法的基本思想

  • 选当前元素，递归的进行后续元素的选择；
  • 将当前元素拿出，再进行一次不放入该元素，递归的进行后续元素的选择。
  • 本来选择放入，再选择不放入的过程，称为回溯试探法。
  • 回溯就是，返回之前的状态，再进行一次递归。
  • 回溯问题的求解一般流程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
List<List<Object>> res = new ArrayList();

public void backtracking(字符串 或 数组, int index, List<Object> tmp....) {
    if(不满足条件) return;
    if(满足条件) {
        res.add(new ArrayList(tmp)); // 将结果存在最终的List<List<Object>> 里面
        return; // 返回
    }
    for(int j=?;j<arr.length();j++) {  // 根据需要确定循环条件
        tmp.add(某一部分);
        记录当前状态S1
        更新状态为S2
        backtracking(用状态S2回溯);
        tmp.remove(tmp.size()-1); // 移除添加的元素
        回到状态S1
    }
}

public List<List<Object>> main(字符串 或 数组) {
    List<Object> tmp = new ArrayList();
    backtracking(需要传递的参数值。一般有源参数，index, tmp....);
    return res;
}

回溯法的相关例题

leetcode 78. 求子集 Subsets

1
2
3
4
5
6
7
8
9
10
11
12
13
Given a set of distinct integers, nums, return all possible subsets.
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
List<List<Integer>> result = new ArrayList();

public void backtracking(int[] nums, int index, List<Integer> tmp_res) {
    result.add(new ArrayList<Integer>(tmp_res));
    for(int i=index;i<nums.length;i++) {
        tmp_res.add(nums[i]);
        backtracking(nums, i+1, tmp_res);
        tmp_res.remove(tmp_res.size()-1);
    }
}

public List<List<Integer>> subsets(int[] nums) {
    List<Integer> tmp_res = new ArrayList();
    backtracking(nums, 0, tmp_res);
    return result;
}

leetcode 90. 带有重复元素求子集 Subsets II

1
2
3
4
5
6
7
8
9
10
11
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Input: nums = [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
  • 将数组先进行排序，然后将得到的结果放入set中去重。
  • 一定要先排序，否则就会出现 [1,2,2,1] 和 [1,1,2,2]，就会出错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Set<List<Integer>> result = new HashSet();

public void backtracking(int[] nums, int index, List<Integer> tmp_res) {
    result.add(new ArrayList<Integer>(tmp_res));
    for(int i=index;i<nums.length;i++) {
        tmp_res.add(nums[i]);
        backtracking(nums, i+1, tmp_res);
        tmp_res.remove(tmp_res.size()-1);
    }
}

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<Integer> tmp_res = new ArrayList();
    backtracking(nums, 0, tmp_res);
    return new ArrayList<>(result);
}
  • 也可以不用set，回溯时遇到相同元素就跳过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<List<Integer>> result = new ArrayList();

public void backtracking(int[] nums, int index, List<Integer> tmp_res) {
    result.add(new ArrayList<Integer>(tmp_res));
    for(int i=index;i<nums.length;i++) {
        tmp_res.add(nums[i]);
        backtracking(nums, i+1, tmp_res);
        tmp_res.remove(tmp_res.size()-1);
        while(i+1<nums.length && nums[i+1]==nums[i]) 
            i += 1;
    }
}

public List<List<Integer>> subsets(int[] nums) {
    Arrays.sort(nums);
    List<Integer> tmp_res = new ArrayList();
    backtracking(nums, 0, tmp_res);
    return result;
}

leetcode 46. 全排列 Permutations

1
2
3
4
5
6
7
8
9
10
11
Given a collection of distinct integers, return all possible permutations.
Input: nums = [1,2,3]
Output:
[
  [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
List<List<Integer>> result = new ArrayList();

public void backtracking(int[] nums, List<Integer> tmp_res, int[] visit) {
    if(tmp_res.size()==nums.length) {
        result.add(new ArrayList(tmp_res));
        return;
    }
    for(int i=0;i<nums.length;i++) {
        if(visit[i]==0) {
            tmp_res.add(nums[i]);
            visit[i] = 1;
            backtracking(nums, tmp_res, visit);
            tmp_res.remove(tmp_res.size()-1);
            visit[i] = 0;
        }
    }
}

public List<List<Integer>> permute(int[] nums) {
    List<Integer> tmp_res = new ArrayList();
    int[] visit = new int[nums.length];
    backtracking(nums, tmp_res, visit);
    return result;
}

leetcode 47. 有重复元素的全排列 Permutations II

1
2
3
4
5
6
7
8
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Input: nums = [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,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
25
26
27
List<List<Integer>> result = new ArrayList();

public void backtracking(int[] nums, List<Integer> tmp_res, int[] visit) {
    if(tmp_res.size()==nums.length) {
        result.add(new ArrayList(tmp_res));
        return;
    }
    for(int i=0;i<nums.length;i++) {
        if(visit[i]==0) {
            tmp_res.add(nums[i]);
            visit[i] = 1;
            backtracking(nums, tmp_res, visit);
            tmp_res.remove(tmp_res.size()-1);
            visit[i] = 0;
            while(i+1<nums.length && nums[i+1]==nums[i]) 
                i += 1;
        }
    }
}

public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    List<Integer> tmp_res = new ArrayList();
    int[] visit = new int[nums.length];
    backtracking(nums, tmp_res, visit);
    return result;
}

leetcode 39. 和为target的所有组合，选择的元素可重复 Combination Sum

1
2
3
4
5
6
7
8
9
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
  • 因为元素可以重复使用，所以backtracking时从 i 开始即可。
  • 而且原始数组中无重复元素，所以直接用list即可，否则使用set.
  • 类似题目1：leetcode 40. Combination Sum II : 元素不可重复使用：backtracking时从 i+1 开始；原始数组有重复元素：使用set即可。
  • 类似题目2：leetcode 216. Combination Sum III：直接初始化原始数组为0-9、判断条件多加一条即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
List<List<Integer>> result = new ArrayList();

public void backtracking(int[] nums, int index, int target, int sum, List<Integer> tmp_res) {
    if(sum>target) return;
    if(sum==target) {
        result.add(new ArrayList(tmp_res));
        return;
    }
    for(int i=index;i<nums.length;i++) {
        tmp_res.add(nums[i]);
        sum += nums[i];
        backtracking(nums, i, target, sum, tmp_res);
        tmp_res.remove(tmp_res.size()-1);
        sum -= nums[i];
    }
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<Integer> tmp_res = new ArrayList();
    backtracking(candidates,0, target, 0, tmp_res);
    return result;
}

leetcode 131. Palindrome Partitioning

1
2
3
4
5
6
7
8
9
10
Given a string s, partition s such that every substring of the partition is a palindrome.
分区s使得分区的每个子字符串都是回文.
Return all possible palindrome partitioning of s.
    
Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]
  • 就是从头开始找回文串，找到一个就放进List里，再判断后面是不是回文串就行了。
  • 回溯都是有模板的，先把模板写出来，然后再填充具体需要判断的内容，就会思路清晰很多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
List<List<String>> res = new ArrayList();
    
public boolean isplindrome(String s) {
    int begin = 0, end = s.length()-1;
    while(begin<=end) {
        if(s.charAt(begin)==s.charAt(end)) {
            begin += 1;
            end -= 1;
        }
        else return false;
    }
    return true;
}

public void backtracking(String s, List<String> tmp) {
    if(s.length()==0) {
        res.add(new ArrayList(tmp));
        return;
    }
    for(int j=0;j<s.length();j++) {
        if(isplindrome(s.substring(0, j+1))) {
            tmp.add(s.substring(0, j+1));
            String tmp_s = s;
            s = s.substring(j+1, s.length());
            backtracking(s, tmp);
            tmp.remove(tmp.size()-1);
            s = tmp_s;
        }
    }
}

public List<List<String>> partition(String s) {
    List<String> tmp = new ArrayList();
    backtracking(s, tmp);
    return res;
}

leetcode 842. Split Array into Fibonacci Sequence

1
2
3
4
5
6
7
Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].
(F.length >= 3) and (F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2).
每个数字不能有前导0.除非单独一个0

Input: "11235813"    Output: [1,1,2,3,5,8,13]
Input: "112358130"   Output: []
Input: "0123"        Output: []

  • try catch 主要是应对字符串长度过长，超出整数的范围。

  • 本来写了三重循环，因为不知道初始的那两个元素怎么加到res里。后来发现：

    if(res.size()<2||res.get(len-1)+res.get(len-2)==value) ，用 res.size()<2 判断一下就行了呀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
List<Integer> res = new ArrayList();
public  boolean backtracking(String S, int k) {
    if(k>=S.length() && res.size()>2) return true;
    else if(k>=S.length()) return false;
    int len = res.size();
    for(int i=k;i<S.length();i++) {
        if(i>k && S.charAt(k)=='0') // 前导0
            return false;
        int value = 0;
        try{value = Integer.parseInt(S.substring(k, i+1));}
        catch(Exception e) {return false;}
        if(len<2 || res.get(len-1)+res.get(len-2)==value) {
            res.add(value);
            boolean flag = backtracking(S, i+1);
            if(flag) return true;
            res.remove(res.size()-1);
        }
        else if(res.get(len-1)+res.get(len-2)<value) // 提前结束
            return false;
    }
    return false;
}

public  List<Integer> splitIntoFibonacci(String S) {
    backtracking(S, 0);
    return res;
}