子集问题

题目链接：
leetcode 78 子集
问题分析：

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序
返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例2：
输入：nums = [0]
输出：[[],[0]]

解决思路：
这个题目可以使用递归解决，对于每个元素，可以选择加入或者不加入某一个子集。每个子集的计算都需要完整遍历所有的元素，可以用index记录当前遍历到的下标，遍历完成则记录子集并返回。代码如下：

public static List<List<Integer>> subsets(int[] nums) {
    List<Integer> tmpResult = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    helper(nums, 0, tmpResult, result);
    return result;
}
public static void helper(int[] nums, int index, List<Integer> tmpResult, List<List<Integer>> result) {
    result.add(new ArrayList<>(tmpResult));
    for (int i= index;i< nums.length;++i) {
        tmpResult.add(nums[i]);
        helper(nums, i + 1, tmpResult, result);
        tmpResult.remove(tmpResult.size() - 1);
    }
}

leetcode 90 子集II
本题目相对于前一题，主要特点是包含重复元素，这可能会导致相等元素放在不同位置，但是却认为是不同子集。解决办法是首先进行排序。

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<Integer> tmpResult = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    helper(nums, 0, tmpResult, result);
    return result;
}
public static void helper(int[] nums, int index, List<Integer> tmpResult, List<List<Integer>> result) {
    if (!result.contains(tmpResult)) {
        result.add(new ArrayList<>(tmpResult));
    }
    for (int i = index; i < nums.length; ++i) {
        if (i > index && nums[i] == nums[i - 1]) {
            continue;
        }
        tmpResult.add(nums[i]);
        helper(nums, i + 1, tmpResult, result);
        tmpResult.remove(tmpResult.size() - 1);
    }
}

组合问题

leetcode 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]]

解决思路：
这个题目是在n个元素中任意挑选k个元素构造数组(元素互不相等)，并返回所有可能的数组。应当使用回溯法，每次挑选一个元素，尝试加入，后剔除该元素返回。递归的出口是构造的数组长度达到了k。
代码如下：

public static List<List<Integer>> combine(int n, int k) {
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        helper(1, n, k, temp, result);
        return result;
    }

    public static void helper(int index, int n, int k, List<Integer> temp, List<List<Integer>> result) {
        if (temp.size() == k) {
            if (!result.contains(temp)) {
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        for (int i = index; i <= n; ++i) {
            if (temp.contains(i)) {
                continue;
            }
            temp.add(i);
            helper(i + 1, n, k, temp, result);
            temp.remove((Integer) i);
        }
    }

排列问题

leetcode 46
题目分析：

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

解决思路：
套用递归框架，如果临时的数组长度达到了原数组长度，就认为是一个符合条件的排列case。每次遍历从0开始，如果元素已经处理，则跳过。
代码如下：

public static List<List<Integer>> permute(int[] nums) {
    if (nums.length == 0) {
        return new ArrayList<>();
    }
    boolean[] visited = new boolean[nums.length];
    List<List<Integer>> res = new ArrayList<>();
    helper(nums, 0, visited, res, new ArrayList<>());
    return res;
}
public static void helper(int[] nums, int index, boolean[] visited, List<List<Integer>> res,
                              List<Integer> temp) {
    if (temp.size() == nums.length) {
        res.add(new ArrayList<>(temp));
        return;
    }
    for (int i = 0; i < nums.length; ++i) {
        if (temp.contains(nums[i])) {
            continue;
        }
        temp.add(nums[i]);
        helper(nums, index + 1, visited, res, temp);
        temp.remove((Integer) nums[i]);
    }
}

区别

最后

以上就是温婉皮带为你收集整理的leetcode子集和组合问题子集问题组合问题排列问题区别的全部内容，希望文章能够帮你解决leetcode子集和组合问题子集问题组合问题排列问题区别所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。