78. 子集

题目描述

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/subsets 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这道题目是求集合,并不是 求极值,因此动态规划不是特别切合,因此我们需要考虑别的方法。

这种题目其实有一个通用的解法,就是回溯法。网上也有大神给出了这种回溯法解题的通用写法,这里的所有的解法使用通用方法解答。除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。

我们先来看下通用解法的解题思路,我画了一张图:

通用写法的具体代码见下方代码区。

关键点解析

  • 回溯法
  • backtrack 解题公式

代码

  • 语言支持:JS,C++

JavaScript Code:

/*
 * @lc app=leetcode id=78 lang=javascript
 *
 * [78] Subsets
 *
 * https://leetcode.com/problems/subsets/description/
 *
 * algorithms
 * Medium (51.19%)
 * Total Accepted:    351.6K
 * Total Submissions: 674.8K
 * Testcase Example:  '[1,2,3]'
 *
 * Given a set of distinct integers, nums, return all possible subsets (the
 * power set).
 *
 * Note: The solution set must not contain duplicate subsets.
 *
 * Example:
 *
 *
 * Input: nums = [1,2,3]
 * Output:
 * [
 * ⁠ [3],
 * [1],
 * [2],
 * [1,2,3],
 * [1,3],
 * [2,3],
 * [1,2],
 * []
 * ]
 *
 */
function backtrack(list, tempList, nums, start) {
    list.push([...tempList]);
    for(let i = start; i < nums.length; i++) {
        tempList.push(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.pop();
    }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const list = [];
    backtrack(list, [], nums, 0);
    return list;
};

C++ Code:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        auto ret = vector<vector<int>>();
        auto tmp = vector<int>();
        backtrack(ret, tmp, nums, 0);
        return ret;
    }

    void backtrack(vector<vector<int>>& list, vector<int>& tempList, vector<int>& nums, int start) {
        list.push_back(tempList);
        for (auto i = start; i < nums.size(); ++i) {
            tempList.push_back(nums[i]);
            backtrack(list, tempList, nums, i + 1);
            tempList.pop_back();
        }
    }
};

相关题目

  • 39.combination-sum
  • 40.combination-sum-ii
  • 46.permutations
  • 47.permutations-ii
  • 90.subsets-ii
  • 113.path-sum-ii
  • 131.palindrome-partitioning

本文分享自微信公众号 - 脑洞前端(fe_lucifer)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能计算时代

「首席架构师推荐」数值分析软件列表

原文:https://en.wikipedia.org/wiki/List_of_numerical-analysis_software

13320
来自专栏墨白的Java基地

java代码查错11道题

大侠们,这有何错误? 答案: 错。abstract method必须以分号结尾,且不带花括号。

8410
来自专栏C语言及其他语言

C++11较C++03的改进

一门语言如果太啰嗦了,不仅会为阅读带来障碍,而且还是许多错误的根源。所以从C语言继承而来的关键词auto在C++11中有了新的定义,可以进行自动类型推断。

10630
来自专栏磐创AI技术团队的专栏

学习OpenCV,新手常会问我的十个问题 | 视觉入门

赶快去检查/配置环境变量,看看有没有把opencv_world+版本号d.dll所在路径到系统环境变量path中去,如果没有问题,重启VS即可

14730
来自专栏光城(guangcity)

C++ STL源码剖析之双向环形链表list

双向环状链表从节点值为3开始插入,红色框表示最后一个节点(end()指向的节点)。黄色线条表示指向前驱节点,黑色线条表示指向后继节点。

12740
来自专栏JAVA人生/面试技巧

JAVA基础复习(重点)

(2)一个.java源文件中可以声明多个类,但是只能有一个public修饰的类,文件名要和public修饰的类名保持一致;

12620
来自专栏微卡智享

Android SurfaceVeiw划矩形截屏存放到RecyclerView中

前一篇文章《Android SurfaceView onTouchEvent进阶操作OpenCV显示》我们已经实现了在SurfaceView中划矩形显示在源图上...

13330
来自专栏C语言及其他语言

【C++语言】 cin和cout的详解

cin是C++编程语言中的标准输入流对象,即istream类的对象。cin主要用于从标准输入读取数据,这里的标准输入,指的是终端的键盘。此外,cout是流的对象...

9810
来自专栏数据魔术师

强化学习读书笔记(10)| On-policy Prediction with Approximation(下)

本讲将继续学习使用on-policy的数据对状态值函数进行逼近,也就是在策略π下估计值函数vπ。

11230
来自专栏JAVA人生/面试技巧

JavaSE笔记

(2)一个.java源文件中可以声明多个类,但是只能有一个public修饰的类,文件名要和public修饰的类名保持一致;

13220

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励