排列&组合问题

[LLancelot]

46. Permutation

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

代码

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        total = len(nums)
        res = []
        permute = deque()
        permute.append([])
        
        for cur in nums:
            permute_len = len(permute)
            for _ in range(permute_len):
                last_permute = permute.popleft()
                for pos in range(len(last_permute) + 1):
                    # insert current number to each position
                    new_permute = list(last_permute)
                    new_permute.insert(pos, cur)
                    if len(new_permute) == total:
                        res.append(new_permute)
                    else:
                        permute.append(new_permute)
        
        return res

78. Subsets

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],
[]
]

代码

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        subsets = []
        subsets.append([])
        
        for cur in nums:
            sublen = len(subsets)
            for i in range(sublen):
                each = list(subsets[i])
                each.append(cur)
                subsets.append(each)
            
        return subsets

784. Letter Case Permutation

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

代码

class Solution(object):
    def letterCasePermutation(self, string):
        """
        :type S: str
        :rtype: List[str]
        """
        permute = []
        permute.append(string)
        
        for i in range(len(string)):
            
            if string[i].isalpha():
                
                permute_len = len(permute)
                
                for j in range(permute_len):
                    
                    each = list(permute[j])
                    each[i] = each[i].swapcase()
                    permute.append("".join(each))
                    
        return permute