算法Day30 餐厅的套餐

餐厅的套餐

Description

假设有一家餐厅，菜单上有n道菜可供选择，现在需要从中选择k道菜组成一份套餐。请设计一个算法，返回所有可能但互不相同的菜品组合。

Input

不同菜品的id各不相同，分别为1,2,3…n,输入内容依次为n和k的值，输入内容之间使用空格隔开
1 ≤ n ≤ 20
1 ≤ k≤n

Output

请你按照数组中元素由小到大的顺序输出结果，若两个数组中前m个元素相同，则根据第m+1个元素判断数组大小

例如：

n = 4 , k = 2时输出顺序为：

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

输出内容要求：

输出结果中不同数字之间使用空格分开并顺序排列即可，输出结果中不含有回车

Sample

代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static ArrayList<Integer> all = new ArrayList<>();
    public static StringBuilder result = new StringBuilder();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int group = scanner.nextInt();
        for(int i = 0;i<n;i++){
            all.add(i+1);
        }//输出
        for(int i =1;i<=n-group+1;i++) {
            ArrayList<String> temp = backTrack(i, group, 1);
            temp.stream().forEach(k->add(k));
        }
        System.out.print(result.toString());
    }
    public static void add(String s){
        result.append(s+" ");
    }
    public static ArrayList<String> backTrack(int start,int group,int s){
        ArrayList<String> temp = new ArrayList<>();
        if(s==group){
            temp.add(String.valueOf(start));
            return temp;
        }
        //1-n
        for(int i = start;i<all.size();i++){
            {
                ArrayList<String> temp1 = backTrack(i + 1, group, s + 1);
                for (String k : temp1) {
                    temp.add(start + " " + k);
                }
            }
        }
        return temp;
    }
}

思路

按照题解使用回溯法，对每一层进行遍历，遍历至group层即可，我这里使用string保存信息。
大规模时使用result保存信息，我首先使用的直接是String类型保存
如图，直接超时
之后采取StringBuilder
在对大长度字符串处理时，还是StringBuilder比较合适