题目地址
https://leetcode.com/problems/subsets/description/
题目描述
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],
[]
]
思路
这道题目是求集合，并不是求极值，因此动态规划不是特别切合，因此我们需要考虑别的方法。
这种题目其实有一个通用的解法，就是回溯法。 网上也有大神给出了这种回溯法解题的 通用写法，这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路，我画了一张图：
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- backtrack 解题公式
代码
/*
* @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;
};
