算法Day30 餐厅的套餐

news/2025/2/23 3:30:48/

餐厅的套餐

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-nfor(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;}
}