[backtracking] backtracking to solve subset problems

• subject ： Give you an array of integers nums , Elements in an array Different from each other . Returns all possible subsets of the array （ Power set ）.
  Solution set You can't Contains a subset of repetitions . You can press In any order Returns the solution set .
• Example 1：
  Input ：nums = [1,2,3]
  Output ：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
  Topic link ：https://leetcode-cn.com/problems/subsets/

#  Iterative method 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ress= [[]]
        for i in range(len(nums)):
            ress += [[nums[i]] + res for res in ress]
        return ress


#  backtracking 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        def backtracking(nums, startindex):
            res.append(path[:])
            for i in range(startindex, len(nums)):
                path.append(nums[i])
                backtracking(nums,i+1)
                path.pop()
        
        backtracking(nums, 0) 
        return res

• subject 2： Give you an array of integers nums , It may contain repeating elements , Please return all possible subsets of the array （ Power set ）.
  Solution set You can't Contains a subset of repetitions . The solution set returned , Subsets can be classified by In any order array .

• Input ：nums = [1,2,2]
  Output ：[[],[1],[1,2],[1,2,2],[2],[2,2]]
  Topic link ：https://leetcode-cn.com/problems/subsets-ii/

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        def backtracking(nums, startindex):
            res.append(path[:])
            for i in range(startindex, len(nums)):
                if i > startindex and nums[i] == nums[i-1]:continue
                path.append(nums[i])
                backtracking(nums, i+1)
                path.pop()
        nums.sort()
        backtracking(nums, 0)
        return res

The second question is different in that it is given nums There are duplicate elements in the array , Therefore, it is necessary to de duplicate each layer , But it can be used repeatedly in the depth traversal in the longitudinal direction , It can be understood as looking for 1 All subsets at the beginning 1xx, Look again 2 All subsets at the beginning 2xx, And so on .
Specific explanations can be found in this article https://blog.csdn.net/m0_60370702/article/details/122981954?spm=1001.2014.3001.5502 This article uses backtracking to solve combinatorial problems , But the de duplication method of the last combinatorial problem is the same as that of this subset .