This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

1. Title Description

You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

Example 1:

Output: input: nums = [1, 2, 3], [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]Copy the code

Example 2:

Nums = [0] Output: [[],[0]]Copy the code

Second, train of thought analysis

First of all, according to the description of the title, we can confirm the following requirements:

  1. Gets all subsets of the input array NUMs
  2. Subsets are not repeated

Then according to the above requirements, we can know that this problem has a way out and a dead end, so we can give priority to backtracking algorithm.

Finally, we can use recursion to simulate all cases, and ensure that the order of the subsets of array elements is consistent with NUMS. After collecting all cases that reach the recursive end point, we can return.

AC code

/** * @param {number[]} nums * @return {number[][]} */ var subsets = function(nums) {const res = [ @param {number[]} Path * @param {number} Path length * @param {number} start position * @return {number[][]} */ const backtrack = (path, L, start) => {// Check whether the current path length is consistent with the specified length // If so, If (path.length === l) {return res.push(path)} i < nums.length; I ++) {backtrack(path.concat(nums[I]), l, I + 1)}} For (let I = 0; i <= nums.length; I ++) {backtrack([], I, 0)} return res};Copy the code

Four,

So what you really need to focus on is, how do you determine the uniqueness and validity of a subset, that is, using start to ensure that the order of the elements is correct

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign