思路分析
回溯算法思路模板：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
子集题目描述
子集题目解题代码
public class Subsets {
/**
* result = []
* def backtrack(路径, 选择列表):
* if 满足结束条件:
* result.add(路径)
* return
* for 选择 in 选择列表:
* 做选择
* backtrack(路径, 选择列表)
* 撤销选择
*/
LinkedList<LinkedList<Integer>> solutions = new LinkedList<>();
public LinkedList<LinkedList<Integer>> subsets(int[] nums) {
if (nums == null) {
return null;
}
LinkedList<Integer> ls = new LinkedList<>();
findResluts(nums, 0, ls);
return solutions;
}
private void findResluts(int[] nums, int start, LinkedList<Integer> integers) {
solutions.add(integers);
for (int i = start; i < nums.length; i++) {
integers.add(nums[i]);
findResluts(nums, i + 1, integers);
integers.pollLast();
}
}
public static void main(String[] args) {
new Subsets().subsets(new int[]{1, 2, 3});
}
}
}
集合题目描述
集合解题代码
class Solution {
List<List<Integer>> combineSolutions = new ArrayList<List<Integer>>();
public List<List<Integer>> combine(int n, int k) {
ArrayList<Integer> ls = new ArrayList<>();
findCombineResult(1,n,k, ls);
return combineSolutions;
}
private void findCombineResult(int start,int n,int k, ArrayList<Integer> integers){
if (integers.size() == k){
combineSolutions.add(new ArrayList<>(integers));
}
for (int i = start; i <= n; i++) {
integers.add(i);
findCombineResult(i + 1, n,k,integers);
integers.remove(integers.size() - 1);
}
}
全排列题目描述
全排列解题代码
class Solution {
private List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
LinkedList<Integer> tracks = new LinkedList<>();
goCal(nums,tracks);
return res;
}
public void goCal(int[] nums,LinkedList<Integer> tracks){
if (nums.length == tracks.size()) {
res.add(new LinkedList<>(tracks));
return;
}
for (int num :nums){
if (tracks.contains(num)){
continue;
}
tracks.add(num);
goCal(nums,tracks);
tracks.removeLast();
}
}
}
