小明很喜欢选数字,现在小明得到 n 个数,他想得到从 n 个数里面选取 k个数的所有方案,由于小明的作业很多,现在没有时间解决这个问题,聪明的你可以帮助小明解决这个问题吗?
输入包括两行数据,第一行包括两个数n(1<=n<25),k(1<=k<=min(n,19)),表示数列数的个数以及要从数列里面选取数的个数。 第二行n个数表示该数列的n个数(0<ai<=100,ai表示数列里面的数,ai可能有重复)。 (两个数之间用空格分开)。
按字典序输出所有的方案(格式参照样例)
4 2 1 1 2 3
1 1 1 2 1 3 2 3
对于10%的数据,1 <= n <= 5, k<= n 对于50%的数据,1 <= n <= 10, k<= n 对于100%的数据,1 <= n <=24, k<= min(n,19) 样例解释 从(1,1,2,3)4个数字里面选2个,有(1,1),(1,2),(1,3),(2,3)四种选法。 为了保证输出的字典序,先对给出的数字进行排序,如果有相同的数字,那么排序后会挨在一起。 此时如果直接套用从 n 个数中选择 m 个数的递归,由于 ai 中有相同的数字,因此会出现完全重复的选择。 为了不出现重复的选择,我们规定如果挨着的两个数字相同,假如前一个没有选,后一个也不能选。 这样需要用一个 bool 数组记录选或未选的状态。剩下的逻辑就同 n 个数中选 m 个数一样了。按照之前的方法递归处理即可