给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
题目求所有解集,典型的回溯法题目,注意剪枝函数是size+1<=k。
按照数值大小循序一次在回溯中形成满足条件的alist。
1 class Solution { 2 public static List<List<Integer>> list; 3 public static List<Integer> alist;; 4 5 public List<List<Integer>> combine(int n, int k) { 6 7 list=new ArrayList<>(); 8 alist=new ArrayList<>(); 9 10 backTrack(n,k,0,0); 11 12 return list; 13 } 14 //size记录目前alist的长度,t代表目前走到的数字 ,size==k时存入list中 15 public static void backTrack(int n, int k,int t,int size){ 16 if(size>=k){ 17 list.add(new ArrayList<>(alist)); 18 }else{ 19 for (int i = t+1; i <= n; i++) { 20 if(size+1<=k){ 21 alist.add(i); 22 backTrack(n,k,i,size+1); 23 alist.remove(new Integer(i)); 24 } 25 } 26 } 27 } 28 }
原文:https://www.cnblogs.com/SEU-ZCY/p/14774542.html