活动地址：CSDN21天学习挑战赛

题目描述

小杨申请了一个保险柜，但是忘记了密码。只记得密码都是数字，而且数字都是不重复的。请根据数字范围和密码的最小数字数量，计算所有可能的密码组合，规则如下：

• 输出的组合都是从可选的数字范围中选取的，且不能重复；
• 输出的密码数字要按照从小到大的顺序排列，密码组合需要按照字典顺序，从小到大的顺序排序；
• 输出的每一个组合的数字的数量要大于等于密码最小数字数量；
• 如果可能的组合为空，则返回“None”。

输入描述

输入的第一行是可能的密码数字列表，数字间以半角逗号分隔；

输入的第二行是密码最小数字数量。

输出描述

可能的密码组合，每种组合显示成一行，每个组合内部的数字以半角逗号分隔，从小到大的顺序排列。输出的组合间需要按照字典顺序排列。

示例

输入

2,3,4

2

输出

2,3

2,3,4

2,4

3,4

思考

原博主 给出的解题思路如下：

1、因为密码是升序的，所以首先要对输入的数字进行升序排序。

2、根据题意是从可选的密码数字列表中选出对应的数量的数字作为密码。也就是从M个字符中取出N个字符的全排列（经典算法）

3、因为最小数字数量是N，所以需要一直遍历到可选密码数字列表的长度，才能得到所以可能的密码组合。

我的思考

题目的意思是从给定的M个数字中取出长度在[N,M]区间内的所有数字组合，并将得到的数字组合按照字典顺序排序。

中间较复杂的问题就是取长度在[N,M]变化的数字组合，简化一下就是取定长L的数字组合，这样就简单多了。

代码实现

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strings = sc.nextLine().split(",");
        int n = sc.nextInt();
        
        //对输入数字进行升序排序
        Arrays.sort(strings);
        //存放数字组合结果
        List<String> list = new ArrayList<>();
        //数组长度l在区间[N,M]间移动
        for(int l=n;i<=strings.length;l++) {
            combine(list,strings,i,new String(),0);
        }
        //将数字组合排序
        Collections.sort(list);
        if(list.size() == 0) {
            System.out.println("None");
        }else {
            list.stream().
                forEach(System.out::println);
        }
    }
  
    public static void combine(List<String> list, String[] str, int n, String res, int index) {
        //list  存储数字组合的结果
        //str  排序后的输入数字组合
        //n  数字组合的长度
        //res  数字组合的字符串
        //index  开始循环的下标
        if(n == 0) {
            //一个数字组合拼接完毕，放入存储
            list.add(res);
        }else{
            //从index处开始循环，一个个拼接
            for(int i=index;i<str.length;i++) {
                //拼接
                if(index == 0)
                	res += str[i];
                else
                    res += "," + str[i];
                //进入下一个分支
                combine(list,str,n-1,res,i+1);
                //将刚刚拼接的最后一个数字剔除
                if(index == 0) {
                	res = res.substring(0, res.length()-1);
                }else {
                    res = res.substring(0,res.length() - - 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

我的理解和收获

本题目中最复杂的部分就是从长度为M的数字中取长度为L的数字组合，这其实很像分治。

比如从1,2,3,4中取两个数字：

先取1，在【2,3,4】中取剩下的一个，有三种；

然后取2，在【3,4】中取剩下的一个，有两种；

然后取3，在【4】中取剩下的一个，有一种；

或者1,2,3,4中取三个数字：

先取1，在【2,3,4】中取剩下的两个：

先取2，在【3,4】中取剩下的一个，有两种；

然后取3，在【4】中取剩下的一个，有一种。

所以这里有三种情况；

然后取2，在【3，4】中取剩下的两个：

先取3，然后在【4】中取剩下的一个，有一种；

所以这里有一种情况。

加一起有四种情况

推广一下就是

从M个字符中取L个字符：

先取一个，在剩下的M-1个字符中取L-1个字符：

先取一个，在剩下的M-2个字符中取L-2个字符：

…

…

总结一下，就是切割字符，然后从剩下的字符中取字符。