回溯算法主要用于解决组合，切割，排序，子集，棋盘问题。
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
public List<List<Integer>> combine(int n, int k) { List<List<Integer>> lists=new ArrayList<>(); if(k<=0||n<k) return lists; ArrayList<Integer> list=new ArrayList<>(); backtack(n,k,1,lists,list); return lists; } public void backtracking(int n,int k,int start,List<List<Integer>> lists,ArrayList<Integer> list){ if(list.size()==k){ lists.add(new ArrayList<>(list)); return; } for(int i=start;i<=n;i++){ // if(list.contains(i)) // continue; list.add(i); backtack(n,k,i+1,lists,list); list.remove(list.size()-1); } }
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> lists=new ArrayList<>(); List<Integer> list=new ArrayList<>(); Arrays.sort(candidates); backtracking(lists,list,target,candidates,0); return lists; } public void backtracking(List<List<Integer>> lists,List<Integer> list,int target,int[] candidates,int start){ Integer collect = list.stream().collect(Collectors.summingInt(Integer::intValue)); if(collect==target) { lists.add(new ArrayList<>(list)); return; } if(collect>target) return; for(int i=start;i<candidates.length;i++){ //大剪枝,如果target -candidates[i] < 0,那么后面的元素都会小于0,需要剪掉 if(candidates[i]>target) continue; //同一层数值相同,需要剪掉,不然会造成重复 if(i > start && candidates[i] == candidates[i-1]){ continue; } list.add(candidates[i]); backtracking(lists,list,target,candidates,i+1); list.remove(list.size()-1); } }
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
输入:k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> lists=new ArrayList<>(); List<Integer> list=new ArrayList<>(); int[] array=new int[]{1,2,3,4,5,6,7,8,9}; int sum = Arrays.stream(array).limit(k).sum(); if(sum>n) return lists; tracking(lists,list,k,n,0,array); return lists; } public void tracking(List<List<Integer>> lists,List<Integer> list,int k,int n,int start,int[] array){ int sum = list.stream().mapToInt(Integer::intValue).sum(); if(sum==n&&list.size()==k){ lists.add(new ArrayList<>(list)); return; } if(sum>n||list.size()>k) return; for(int i=start;i<array.length;i++){ if(array[i]>n) continue; list.add(array[i]); tracking(lists,list,k,n,i+1,array); list.remove(list.size()-1); } }
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
public List<List<Integer>> permute(int[] nums) { List<List<Integer>> lists=new ArrayList<>(); if(nums.length==0) return lists; ArrayList<Integer> list=new ArrayList<>(); backtracking(lists,list,nums); return lists; } public void backtracking(List<List<Integer>> lists,ArrayList<Integer> list,int[] nums){ if(list.size()==nums.length){ lists.add(new ArrayList<>(list)); return; } for(int i=0;i<nums.length;i++){ if(list.contains(nums[i])) continue; list.add(nums[i]); backtracking(lists,list,nums); list.remove(list.size()-1); } }
已知一个长度为 N 的数组：A1, A2, A3, ...AN 恰好是 1 ∼ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个，最多 N 个) 连续的子数组，并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法：
{1}{3}{2}{4}：每个单独的数显然是 (长度为 1 的) 一段连续的自然数。
{1}{3, 2}{4}：{3, 2} 包含 2 到 3，是 一段连续的自然数，另外 {1} 和 {4} 显然也是。
{1}{3, 2, 4}：{3, 2, 4} 包含 2 到 4，是 一段连续的自然数，另外 {1} 显然也是。
{1, 3, 2}{4}：{1, 3, 2} 包含 1 到 3，是 一段连续的自然数，另外 {4} 显然也是。
{1, 3, 2, 4}：只有一个子数组，包含 1 到 4，是 一段连续的自然数。
输入格式
第一行包含一个整数 N。第二行包含 N 个整数，代表 A 数组。
输出格式
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
样例输入
复制
4 1 3 2 4
样例输出
复制
5
public class m { static int result=0; public static void main(String[] args) { Scanner sc=newScanner(System.in); int n=sc.nextInt(); int[] arr=newint[n]; for(int i=0;i<arr.length;i++) arr[i]=sc.nextInt(); backtreeing(arr, 0); System.out.println(result); } public static void backtreeing(int arr[],int start) { if(start==arr.length) { result++; return; } for(int i=start;i<arr.length;i++) { if(check(arr, start, i)) { backtreeing(arr, i+1); } } } private static boolean check(int[] a, int l, int r) { intmax= Integer.MIN_VALUE, min = Integer.MAX_VALUE; for (int i= l; i <= r; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } return max - min == r - l; } }
