首页 > 其他 > 详细

力扣77. 组合

时间:2021-05-17 00:21:21      阅读:44      评论:0      收藏:0      [点我收藏+]

题目:

给定两个整数 n 和 k,返回 1 ... 中所有可能的 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 }

 

技术分享图片

 

力扣77. 组合

原文:https://www.cnblogs.com/SEU-ZCY/p/14774542.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!