77. 组合

参考77. 组合 - 力扣（Leetcode）。

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

输入：n = 4, k = 2
输出：[[2,4], [3,4], [2,3],[1,2],[1,3], [1,4],]
输入：n = 1, k = 1
输出：[[1]]

解题思路

• 位集合：数据范围较小可使用位集合进行选或不选的递归。
• 回溯：使用队列进行选的回溯或不选的递归。

位集合

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(ans,n,k,0,0,0);
        return ans;
    }
    void dfs(List<List<Integer>> ans,int n,int k, int i,int hash,int count){
        if(count == k) {
            List<Integer> list = new ArrayList<>();
            int num = 1;
            while(hash != 0) {
                if((hash & 1) == 1) list.add(num);
                hash >>= 1;
                num ++;
            }
            ans.add(list);
            return;
        }
        //选
        dfs(ans,n,k,i+1,hash|(1<<i),count+1);
        //不选
        if(count + n-i > k) dfs(ans,n,k,i+1,hash,count);
    }
}

回溯

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(ans,n,k,1,new ArrayList<Integer>());
        return ans;
    }
    void dfs(List<List<Integer>> ans,int n,int k, int i,List<Integer> res){
        if(res.size() == k) {
            ans.add(new ArrayList<>(res));
            return;
        }
        //选
        res.add(i);
        dfs(ans,n,k,i+1,res);
        res.remove(res.size()-1);
        //不选
        if(res.size() + n-i >= k) dfs(ans,n,k,i+1,res);
    }
}

2023.06.17