组合排序回溯编程题集合（leetcode)

回溯算法主要用于解决组合，切割，排序，子集，棋盘问题。

给定两个整数 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;
        }

}