leet code 77. 组合

77. 组合

题目描述

给定两个整数 n 和 k

返回范围 [1, n] 中所有可能的 k 个数的组合。

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

示例 1：

输入：n = 4, k = 2

输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

示例 2：

输入：n = 1, k = 1

输出：[[1]]

提示：
● 1 <= n <= 20
● 1 <= k <= n

题目解析

• 组合问题，从数字1到数字n 每一个数字都可以作为根
• 很显然数字还不能重复使用

code 1

class Solution {

    private List<List<Integer>> ans;

    // 标记被使用过的数字
    private boolean[] used;

    private int n;

    private int k;

    public List<List<Integer>> combine(int n, int k) {
        // 初始化结果集  和  标记集
        ans = new ArrayList<>();
        used = new boolean[n + 1];

        // 初始化全局变量
        this.n = n;
        this.k = k;

        List<Integer> local = new ArrayList<>();

        // 1 ：表示从 1 开始选择
        // local ：保存选择路径上的元素
        dfs(local, 1);


        return ans;
    }

    private void dfs(List<Integer> local, int idx) {
        // 如果剩下的数全部都选择不够 k 个数了直接返回
        if(local.size() + (n - idx + 1) < k) {
            return;
        }
        // 足够 k 个数了
        if(local.size() == k) {
            // 加入到结果集合中
            ans.add(new ArrayList<>(local));
            return;
        }
        // 相当于遍历有序数组.
        for(int i = idx;i <= n;i++) {
            if(used[i]){ 
                continue;
            }
            // 选择当前元素
            local.add(i);
            // 标记
            used[i] = true;

            // 深度搜索
            dfs(local, i + 1);

            // 取消标记
            used[i] = false;
            // 撤销选择
            local.remove(local.size() - 1);
        }
    }

}

code 2

class Solution {

    private List<List<Integer>> ans;

    private int n;

    private int k;

    public List<List<Integer>> combine(int n, int k) {
        // 初始化结果集  和  标记集
        ans = new ArrayList<>();

        // 初始化全局变量
        this.n = n;
        this.k = k;

        List<Integer> local = new ArrayList<>();

        // 1 ：表示从 1 开始选择
        // local ：保存选择路径上的元素
        dfs(local, 1);
    

        return ans;
    }

    private void dfs(List<Integer> local, int idx) {
        // 如果剩下的数全部都选择不够 k 个数了直接返回
        if(local.size() + (n - idx + 1) < k) {
            return;
        }
        // 足够 k 个数了
        if(local.size() == k) {
            // 加入到结果集合中
            ans.add(new ArrayList<>(local));
            return;
        }

        // 对于每一个元素面临 2 种情况，选 or 不选
        
        // 不选择当前元素
        dfs(local, idx + 1);

        // 选择当前元素
        local.add(idx);
        dfs(local, idx + 1);
        local.remove(local.size() - 1);
    }

}