LeetCode-排列组合题

LeetCode31 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。

---

思路：

1. 从右向左找到第一个开始降序的数字a
2. 从右向左找到第一个比a大的数字b
3. 交换a和b
4. 反转a后面的数组

---

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n==0 or n==1:
            return
        pivot = -1
        for j in range(n-2,-1,-1):
            if nums[j]<nums[j+1]:
                pivot = j
                break
        if pivot != -1:
            j = n-1
            while j>pivot:
                if nums[j]>nums[pivot]:
                    break
                j -= 1
            nums[pivot],nums[j] = nums[j],nums[pivot]
        
        r = n-1
        j = pivot+1
        while r>j:
            nums[r],nums[j] = nums[j],nums[r]
            r -=1
            j += 1
        return

LeetCode39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates = sorted(candidates)
        self.dfs(candidates,0,res,[],target)
        return res
        
    def dfs(self,candidates,start,res,cur,target):
        if target<0:return
        elif 0==target:
            res.append(cur)
            return
        else:
            for i in range(start,len(candidates)):
                self.dfs(candidates,i,res,cur+[candidates[i]],target-candidates[i])

LeetCode40. 组合总和 II(不能重复使用同一个数)

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res=[]
        candidates = sorted(candidates)
        self.dfs(candidates,-1,res,[],target)
        return res
    def dfs(self,candidates,start,res,cur,target):
        if target<0:return
        elif target==0:
            res.append(cur)
            return
        else:
            for i in range(start+1,len(candidates)):
                if i>start+1 and candidates[i]==candidates[i-1]:continue
                self.dfs(candidates,i,res,cur+[candidates[i]],target-candidates[i])

LeetCode46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res,cur = [],[]
        n = len(nums)
        self.dfs(nums,res,cur,n)
        return res
        
    def dfs(self,nums,res,cur,n):
        if n==0:
            res.append(cur)
        elif n>0:
            for i in range(len(nums)):
                self.dfs(nums[:i]+nums[i+1:],res,cur+[nums[i]],n-1)

LeetCode47. 全排列 II(有重复数字)

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res,cur = [],[]
        n = len(nums)
        nums = sorted(nums)
        self.dfs(nums,res,cur,n)
        return res
        
    def dfs(self,nums,res,cur,n):
        if n==0:
            res.append(cur)
        elif n>0:
            for i in range(len(nums)):
                if i<len(nums)-1 and nums[i]==nums[i+1]:continue
                self.dfs(nums[:i]+nums[i+1:],res,cur+[nums[i]],n-1)

LeetCode77. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res,cur = [],[]
        self.dfs(n,k,cur,0,res)
        return res
    def dfs(self,n,k,cur,start,res):
        if k==0:
            res.append(cur)
            return
        if k>0:
            for i in range(start+1,n+1):
                self.dfs(n,k-1,cur+[i],i,res)

LeetCode78. 子集

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

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res,cur = [],[]
        self.dfs(nums,cur,0,res)
        return res
    def dfs(self,nums,cur,start,res):
        res.append(cur)
        for i in range(start,len(nums)):
            self.dfs(nums,cur+[nums[i]],i+1,res)

LeetCode90. 子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res,cur = [],[]
        nums = sorted(nums)
        self.dfs(nums,res,cur)
        
        return res
        
    def dfs(self,nums,res,cur):
        res.append(cur)
        for i in range(len(nums)):
            if i >0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[i+1:],res,cur+[nums[i]])