黄色操逼网站,午夜中文无码,亚洲国产视频中文字幕日不卡在线观看高清无码 ,人妻久久久久免费肉丝足交,五月天婷婷电影,国产精品午夜未成人免费观看,中文字幕+乱码+中文乱码视频在线观看,青娱乐成人在线视频

題目鏈接

https://leetcode-cn.com/problems/combinations/

題目描述

給定兩個整數(shù) n 和 k，返回 1 ... n 中所有可能的 k 個數(shù)的組合。

示例:

輸入: n = 4, k = 2輸出:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]

解題方案

思路

標簽：回溯與剪枝
n表示范圍為1...n，balance表示剩余空間，start表示開始位置，list為回溯列表
判斷balance == 0，如果為0則代表list中已經(jīng)存入k個數(shù)，拷貝list存入結(jié)果ans中
如果不為0，從start位置開始遞歸調(diào)用，現(xiàn)將當前位置數(shù)據(jù)加入list中，并進入下一層，等待返回后將本層加入的數(shù)據(jù)移除，本質(zhì)就是樹的構造過程
其中循環(huán)結(jié)束條件默認為最大值到n，這里可以優(yōu)化進行剪枝，比如n=4，k=3時，如果列表從start=3也就是[3]開始，那么該組合一定不存在，因為至少要k=3個數(shù)據(jù)，所以剪枝臨界點為n-balance+1

圖解

代碼

class Solution {    private List> ans = new ArrayList<>();    public List> combine(int n, int k) {        getCombine(n, k, 1, new ArrayList<>());        return ans;    }        public void getCombine(int n, int k, int start, List list) {        if(k == 0) {            ans.add(new ArrayList<>(list));            return;        }        for(int i = start;i <= n - k + 1;i++) {            list.add(i);            getCombine(n, k - 1, i+1, list);            list.remove(list.size() - 1);        }    }}

畫解算法 77-組合

題目鏈接

題目描述

解題方案

思路

圖解

代碼

推薦閱讀