[LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters

 Problem : https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

This problem is kind of knapsack problem.  For each sub-string, we can pick it if it does not introduce duplicated character or not pick it and use the rest sub-string to form a longer string.

Time Complexity = O ( N ** 2 ).  N = len(arr)

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        # filter sub-string with duplicated characters
        wordsets = [set(w) for w in arr if len(set(w)) == len(w)]
        
        def helper(start, mask):
            if start >= len(wordsets):
                return len(mask)
            
            # don't pick current sub-string if it introduces duplicated characters
            if mask & wordsets[start]:
                return helper(start + 1, mask)
            
            picked = helper(start + 1, mask | wordsets[start])
            notPicked = helper(start + 1, mask)
            
            return picked if picked > notPicked else notPicked
        
        return helper(0, set())

[LeetCode] 894. All Possible Full Binary Trees

 Problem : https://leetcode.com/problems/all-possible-full-binary-trees/

A full binary tree must have odd number of nodes.  So we can find all possible left and right sub trees to construct the needed trees.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    @cache
    def allPossibleFBT(self, n: int) -> List[TreeNode]:
        if n == 1:
            return [TreeNode()]
        
        result = []
        
        for i in range(1, n+1):
            left = i - 1
            right = n - i
            
            if left % 2 == 1 and right % 2 == 1:
                lts = self.allPossibleFBT(left)
                rts = self.allPossibleFBT(right)
                
                for lt in lts:
                    for rt in rts:
                        result.append(TreeNode(left=lt, right=rt))
        
        return result

[LeetCode] 386. Lexicographical Numbers

 Problem : https://leetcode.com/problems/lexicographical-numbers/

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        
        def backtrack(x):
            if x <= n:
                result.append(x)
            
                for t in range(10):
                    if x * 10 + t <= n:
                        backtrack(x*10 + t)
                    else:
                        break
            
            return result

        result = []
        for x in range(1, 10):
            if x <= n:
                backtrack(x)
        
        return result

[LeetCode] 282. Expression Add Operators

 Problem : https://leetcode.com/problems/expression-add-operators/

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        result = []
        
        def helper(num, diff, curNum, partial):
            if len(num) == 0 and curNum == target:
                result.append(partial)
                return
            
            for i in range(1, len(num)+1):
                cur = num[:i]
                
                
                if len(cur) > 1 and cur[0] == '0':
                    return
              
                if len(partial) == 0:
                    helper(num = num[i:], diff = int(cur), curNum = int(cur), partial = cur)
                else:
                    # A + B
                    helper(num = num[i:], diff = int(cur), curNum = curNum + int(cur), partial = partial + '+' + cur)
                
                    # A - B
                    helper(num = num[i:], diff = -1 * int(cur), curNum = curNum - int(cur), partial = partial + '-' + cur)
        
                    # A * B
                    helper(num = num[i:], diff = diff * int(cur), curNum = curNum - diff + diff * int(cur), partial = partial + '*' + cur)
                
        helper(num, 0, 0, "")
        
        return result

Instead of saving the diff of previous calculation, we may postpone the process of '+' operator.  The '-' operator can be considered as add a negative number.

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]: 
        result = []
        
        def backtrack(start, preNum, curNum, expr):
            """
            calculate preNum + curNum [operator] tmp
            [operator] = +, -, *
            """
            if start == len(num):
                if preNum + curNum == target:
                    result.append(expr)
                return
            
            tmp = 0
            for i in range(start, len(num)):
                tmp = tmp * 10 + int(num[i])
                
                # *  multiplication is the highest priority operator, we get the result of curNum * tmp right away.
                backtrack(i+1, preNum, curNum * tmp, expr + '*' + num[start:i+1])
                
                # +  addition is a low priority operator, save current partial result and postpone the calculation of + tmp
                backtrack(i+1, curNum + preNum, tmp, expr + '+' + num[start:i+1])
                
                # -  substruction is a low priority operator, save current partial result and postpone the calculation of + (-tmp)
                backtrack(i+1, curNum + preNum, -tmp, expr + '-' + num[start:i+1])
                
                if num[start] == '0':
                	# break to avoid number with leading '0'
                    break
            
        
        tmp = 0
        for i in range(len(num)):
            tmp = tmp * 10 + int(num[i])
            backtrack(i+1, 0, tmp, num[:i+1])
            if num[0] == '0':
                # break to avoid number with leading '0'
                break
        
        return result

Edited on 03/16/2021. An optimized version.

Edited on 09/18/20201. Add more comment to the 2nd solution which postpone the process of '+' operator.

[LeetCode] 216. Combination Sum III

Problem : https://leetcode.com/problems/combination-sum-iii/

Use backtracking approach. Pick up one number at a time until find a valid combination, then it into the result bucket.

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        
        result = []
        
        def backtracking(start, sums, partial):
            if len(partial) == k and sums == n:
                result.append(partial)
                return
            
            for i in range(start, 10):
                if sums + i <= n:
                    backtracking(i+1, sums+i, partial + [i])
        
        backtracking(1, 0, [])
        return result

[LeetCode] 212. Word Search II

Problem : https://leetcode.com/problems/word-search-ii/

Tire + Backtracking approach :

class Node:
    def __init__(self, val='', end=False):
        self.val = val
        self.end = end
        self.nxt = {}

class Trie:
    def __init__(self):
        self.root = Node()
    
    def add(self, word):
        p = self.root
        
        for w in word:
            if w not in p.nxt:
                p.nxt[w] = Node(w)
            
            p = p.nxt[w]
            
        p.end = True
        

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ROW = len(board)
        COLUMN = len(board[0])
        
        trie = Trie()
        
        for word in words:
            trie.add(word)
        
        result = set()
        visited = [[False] * COLUMN for _ in range(ROW)]
        
        def dfs(y, x, tmp, p):
            if p.end:
                result.add(tmp)
            
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ny, nx = y + dy, x + dx
                
                if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny][nx] and board[ny][nx] in p.nxt:
                    visited[ny][nx] = True
                    dfs(ny, nx, tmp + board[ny][nx], p.nxt[board[ny][nx]])
                    visited[ny][nx] = False
        
        for y in range(ROW):
            for x in range(COLUMN):
                if board[y][x] in trie.root.nxt:
                    visited[y][x] = True
                    dfs(y, x, board[y][x], trie.root.nxt[board[y][x]])
                    visited[y][x] = False
        
        return result

Edited on 10/9/2021. Update for simpler code.

[LeetCode] 140. Word Break II

Problem : https://leetcode.com/problems/word-break-ii/

Use memorization approach to cache the result of,  starting from position "start", whether it is possible to break string into words in dictionary.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDictSet = set(wordDict)
        result = []
        
        @lru_cache(maxsize = None)
        def backtracking(start):
            if start == len(s):
                return [[]]
            
            result = []
            for i in range(start, len(s)):
                tmp = s[start:i+1]
                if tmp in wordDictSet:
                    partials = backtracking(i+1)
                    for p in partials:
                        result.append([tmp] + p)
                    
            return result
        
        result = backtracking(0)
        
        return map(lambda x : " ".join(x), result)

[LeetCode] 132. Palindrome Partitioning II

Problem : https://leetcode.com/problems/palindrome-partitioning-ii/

This problem includes 2 sub-problems.

Let isPalindrome[i][j] = True if s[i:j+1] is a palindrome string.

The transformation formula is

isPalindrome[i][j] = True,  when:

1)  s[i] == s[j]  and j - i <= 2     # i.e. "aa" or "aba"

2)  s[i] == s[j]  and isPalindrome[i+1][j-1] == True.   # i.e.  "a ****  a"

Let minCut[i] = min cut needed for s[0:i+1]

For any s[0:i+1], it can be split into 2 parts:  s[0:j] and s[j:i+1]

if s[j : j + 1] is a palindrome,  then minCut[i] = min( minCut[i], minCut[j-1] + 1 )

if s[0: j + 1] is already a palindrome, minCut[i] = 0

class Solution:
    def minCut(self, s: str) -> int:
        if not s:
            return 0
        
        # isPalindrome[i][j] = True if s[i:j+1] is palindrome string
        isPalindrome = [[False] * len(s) for _ in range(len(s))]
        
        for j in range(len(s)):
            for i in range(j+1):
                if s[i] == s[j] and (j - i <= 2 or isPalindrome[i+1][j-1] == True):
                    isPalindrome[i][j] = True
        
        
        # minCut[i] = min cut of s[0:i+1]
        minCut = [i for i in range(len(s))]
        
        for i in range(len(s)):
            for j in range(i+1):
                if isPalindrome[j][i]:
                    if j == 0:
                        # s[0:i+1] is already a palindrome
                        # no need to cut
                        minCut[i] = 0
                        break
                    
                    minCut[i] = min(minCut[i], minCut[j-1] + 1)
    
        return minCut[-1]

The top-down memorization + backtracking solution:

class Solution:
    def minCut(self, s: str) -> int:
        
        @cache
        def isPalindrome(left, right):
            if left >= right:
                return True
            
            if right - left == 1:
                return True
                
            if s[left] == s[right-1] and isPalindrome(left+1, right-1):
                return True
            
            return False
        
        @cache
        def helper(left, right):
            if isPalindrome(left, right):
                # s[left:right] is already a palindrome. no need to cut.
                return 0
            
            result = right - left - 1
            
            for mid in range(left+1, right):
                if isPalindrome(left, mid):
                    # s[left:mid] is palindrome, we can try to cut it at 'mid' and calculate the least cut of rest of string
                    result = min(result, 1 + helper(mid, right))
            
            return result
        
        return helper(0, len(s))

Edited on 08/07/2021. Add the top-down memorization + backtracking solution.

[LeetCode] 131. Palindrome Partitioning

Problem : https://leetcode.com/problems/palindrome-partitioning/

Memorization Solution:

Step 1, find the first palindrome and put it to current partial result.

Step 2, repeat step1 to find palindrome in the rest string and append to partial result.

Stop repeating step 1 when rest string is empty.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        
        @lru_cache(maxsize = None)
        def isPalindrome(start, end):
            while start < end:
                if s[start] != s[end]:
                    return False
                start += 1
                end -= 1
            
            return True
        
        def helper(start, partial):
            if start == len(s):
                result.append(partial)
                return
            
            for i in range(start, len(s)):
                if isPalindrome(start, i):
                    helper(i+1, partial + [s[start:i+1]])
                   
        helper(0, [])
        
        return result

DP + DFS solution:

class Solution {
    int N;
    boolean[][] palindrome;
    Map<Integer, List<List<String>>> memo = new HashMap<>();
    
    public List<List<String>> partition(String s) {
        N = s.length();
        palindrome = new boolean[N][N];
        
        for (int left = N-1; left >= 0; left--) {
            for (int right = N-1; right >= left; right--) {
                palindrome[left][right] = s.charAt(left) == s.charAt(right) && (right - left <= 1 || palindrome[left+1][right-1]);
            }
        }
        
        return helper(s, 0);
    }
    
    List<List<String>> helper(String s, int start) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        
        List<List<String>> result = new ArrayList<>();
        
        if (start >= N) {
            List<String> tmp = new ArrayList<>();
            result.add(tmp);
           
            return result;
        }
        
        for (int i = start; i < N; i++) {
            if (palindrome[start][i]) {
                for (List<String> suffix : helper(s, i+1)) {
                    List<String> tmp = new ArrayList<>();
                    tmp.add(s.substring(start, i+1));
                    tmp.addAll(suffix);
                    result.add(tmp);
                }
            }
        }
        
        memo.put(start, result);
        
        return result;
    }
}

DP solution:

Time complexity = O( N ** 2 )

class Solution {
    public List<List<String>> partition(String s) {
        int N = s.length();
        boolean[][] palindrome = new boolean[N][N];
        
        // memo[i] = palindrome partitions of s[i:]
        List<List<List<String>>> memo = new ArrayList<>(N+1);
        
        for (int i = 0; i < N; i++) {
            memo.add(new ArrayList<List<String>>());
        }
        
        // Add an empty partition list for position 'N'
        // memo[N] = [[]]
        memo.add(Arrays.asList(Collections.emptyList()));
        
        for (int left = N-1; left >= 0; left--) {
            for (int right = N-1; right >= left; right--) {
                palindrome[left][right] = s.charAt(left) == s.charAt(right) && (right - left <= 1 || palindrome[left+1][right-1]);
                
                if (palindrome[left][right]) {
                    // s[left:right+1] is a palindrome
                    // use it to expand the palindrome partitions of s[right+1:]
                    for (List<String> suffix : memo.get(right+1)) {
                        List<String> tmp = new ArrayList<>();
                        tmp.add(s.substring(left, right+1));
                        tmp.addAll(suffix);
                        memo.get(left).add(tmp);
                    }
                }
            }
        }
        
        // return palindrome partitions of s[0:]
        return memo.get(0);
    }
}

Edited on 04/13/2021. Add DP solution.

Edited on 01/04/2022. Refactor the DP + DFS solution.

Edited on 01/04/2022. Refactor the DP solution.

[LeetCode] 113. Path Sum II

Problem : https://leetcode.com/problems/path-sum-ii/

Use backtracking approach to collect all valid paths.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:    
        def allPaths(node, tmp):
            tmp.append(node.val)
            
            if not node.left and not node.right:
                yield tmp[:]
            else:
                if node.left:
                    yield from allPaths(node.left, tmp)
                if node.right:
                    yield from allPaths(node.right, tmp)
            
            tmp.pop()
        
        return [path for path in allPaths(root, []) if sum(path) == targetSum] if root else []

An iterative solution based on stack

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        if not root: return []
        result = []
        
        stack = [(root, [root.val])]
        
        while stack:
            node, path = stack.pop()
           
            if not node.left and not node.right:
                if sum(path) == targetSum:
                    result.append(path)
            else:
                if node.right:
                    stack.append((node.right, path + [node.right.val]))
                if node.left:
                    stack.append((node.left, path + [node.left.val]))
        
        return result

Edited on 04/22/2021. Update the DFS solution with 'yield' and 'yield from'.

Edited on 08/04/2021. Small refactor to the DFS solution.

Edited on 08/04/2021. Add the stack based iterative solution.

[LeetCode] 95. Unique Binary Search Trees II

Problem : https://leetcode.com/problems/unique-binary-search-trees-ii/

In BST,  each node is larger than every nodes in its left sub-tree and smaller than every nodes in its right sub-tree.  We should use every valid integer as root node and create BST recursively.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        
        def helper(left, right):
            if left == right:
                return [TreeNode(val=left)]
            elif left > right:
                return [None]
            else:
                return [TreeNode(val=pivot, left=l, right=r) for pivot in range(left, right+1) for l in helper(left, pivot - 1) for r in helper(pivot+1, right)]

        return helper(1, n)

Edited on 09/02/2021. Update a simpler solution.

[LeetCode] 93. Restore IP Addresses

Problem : https://leetcode.com/problems/restore-ip-addresses/

Use backtracking approach. For every digit, it can be either used as a new segment or used to extend the last segment.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        
        def backtracking(i, partial):
            if i == len(s):
                if len(partial) == 4:
                    ip = ".".join(partial)
                    result.append(ip)
                return
            
            # append new segment
            if len(partial) < 4:
                partial.append(s[i])
                backtracking(i+1, partial)
                partial.pop()
         
            # extend last segment
            if partial and partial[-1] != '0' and int(partial[-1] + s[i]) <= 255:
                partial[-1] = partial[-1] + s[i]
                backtracking(i+1, partial)
                partial[-1] = partial[-1][:-1]

        
        backtracking(0, [])
        
        return result

[LeetCode] 90. Subsets II

Problem : https://leetcode.com/problems/subsets-ii/

Consider the code is traversing a tree. On each step, the code has 2 options that are pick or not pick number on this position.

Time Complexity =  O ( len(nums) * len(nums) * log (len(nums) )  )

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        
        def backtracking(start, partial, maxSize):
            if len(partial) == maxSize:
                result.append(partial)
                return
            
            for i in range(start, len(nums)):
                # value of number[i-1] has been picked
                # skip number[i-1] to avoid duplicate subsets
                if i > start and nums[i] == nums[i-1]:
                    continue
                    
                backtracking(i + 1, partial + [nums[i]], maxSize)
        
        
        for i in range(len(nums)+1):
            backtracking(0, [], i)
            
        
        return result

An iterative solution which uses hashset to filter the duplicates.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = set([()])
        nums.sort()
                
        for i, n in enumerate(nums):
            tmp = result.copy()
            for prefix in tmp:
                result.add(prefix + (n,))
                       
        return result

Edited on 08/03/2021. Add the hashset based iterative solution.

[LeetCode] 78. Subsets

Problem : https://leetcode.com/problems/subsets/

This looks like a follow-up problem of 77. Combinations

Use the same approach to generate the combinations with max length from 0 to len(nums).

Backtracking Solution:

Time Complexity = O ( N ** 2 * N )

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtracking(start, partial, maxLen):
            if len(partial) == maxLen:
                result.append(partial)
                
            
            for i in range(start, len(nums)):
                # pick nums[i]
                backtracking(i+1, partial + [nums[i]], maxLen)
                # not pick nums[i]
        
        
        # generate combination with max length from 0 to len(nums)
        for i in range(len(nums) + 1):
            backtracking(0, [], i)
        
        return result

DFS Solution :

Consider the code is traversing a tree. On each node it has 2 options to pick or not pick the number on this node.

Time Complexity = O ( N ** 2 * N ).   

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        result = []
        
        def dfs(start, partial):
            if start == len(nums):
                result.append(partial)
                return
            
            # not pick nums[start]
            dfs(start + 1, partial)
            
            # pick nums[start]
            dfs(start + 1, partial + [nums[start]])
            
        dfs(0, [])
        
        return result

Cascading Solution:

Get new subsets by append current number to the subsets generated by the last step.

Time Complexity = O ( N ** 2 * N )

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        result = [[]]
        
        for n in nums:
            for i in range(len(result)):
                # append current number to subsets 
                # generated by last step
                result.append(result[i] + [n])
        
        return result

[LeetCode] 77. Combinations

Problem : https://leetcode.com/problems/combinations/

Equivalent to traverse a tree constructed with number 1 ~ n. On each step the code may chose pick or not pick the number on this step.

Time Complexity : O ( N * (N - 1) .. (N-K) ) 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def backtrack(x, partial):
            if len(partial) == k:
                result.append(partial)
                return
             
            if x <= n:
                # pick x
                backtrack(x+1, partial + [x])
                
                # not pick x
                backtrack(x+1, partial)
            
        backtrack(1, [])
        return result
        

Another backtracking solution:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def backtrack(x, partial):
            if len(partial) == k:
                result.append(partial)
                return
             
            for i in range(x, n+1):
            	# pick number i
                backtrack(i+1, partial + [i])
                # not pick number i
            
        backtrack(1, [])
        return result

BFS solution:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        if k == 0: return []
        if k == n: return [[i+1 for i in range(n)]]
                   
        result = []
        queue = deque([[i+1] for i in range(n)])
        
        while queue:
            combo = queue.popleft()
            
            if len(combo) == k:
                result.append(combo)
            else:
                for i in range(combo[-1] + 1, n+1):
                    queue.append(combo + [i])
        
        return result

[LeetCode] 52. N-Queens II

Problem : https://leetcode.com/problems/n-queens-ii/

Same to the 51. N-Queens

class Solution:
    def totalNQueens(self, n: int) -> int:
        
        @cache
        def getOccupies(y, x):
            occupies = [(y, x)]
            for dy, dx in [(1,0), (0,1), (1,1), (1,-1)]:
                tmpY, tmpX = y+dy, x+dx
                
                while 0 <= tmpY < n and 0 <= tmpX < n:
                    occupies.append((tmpY, tmpX))
                    tmpY += dy
                    tmpX += dx
            
            return occupies
        
        
        def backtrack(y, board):
            if y == n:
                yield 1
            else:
                for x in range(n):
                    if board[y][x]:
                        # skip this position as it has been occupied
                        continue
                    
                    myOccupies = getOccupies(y,x)
                    
                    for py, px in myOccupies:
                        board[py][px] += 1
                    
                    yield from backtrack(y+1, board)
                    
                    for py, px in myOccupies:
                        board[py][px] -= 1
        
        board = [[0] * n for _ in range(n)]
        return sum(backtrack(0, board))

Edited on 05/22/2021. Use memorization to simplify the code for checking whether one position is valid to put a Queen.

Edited on 05/29/2021. Optimize performance by only marking positions on right and on rows below.

[LeetCode] 51. N-Queens

Problem : https://leetcode.com/problems/n-queens/

A typical backtracking problem. Simulate the process to check if it is valid to put queen on current position. Otherwise, return to the last state.

 

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [[0] * n for _ in range(n)]
        result = []
        
        def toBoard(queens):
            return [''.join(['Q' if x == queens[y] else '.' for x in range(n)]) for y in range(n)]
        
        @cache
        def getOccupied(y, x):
            occupied = [(y,x)]
            
            # because we scan from left to right and top to bottom
            # it only needs to mark the poisition on right and on rows below
            for dy, dx in [(1,0), (0,1), (1, 1), (1, -1)]:
                tmpY, tmpX = y + dy, x + dx
                while 0 <= tmpY < n and 0 <= tmpX < n:
                    occupied.append((tmpY, tmpX))
                    tmpY += dy
                    tmpX += dx
                
            return occupied
        
        def backtrack(y, queens):
            if y == n:
                yield toBoard(queens)
            else:
                for x in range(n):
                    if board[y][x]:
                        continue
                    
                    myOccupied = getOccupied(y, x)
                    
                    for occupiedY, occupiedX in myOccupied:
                        board[occupiedY][occupiedX] += 1
                        
                    queens.append(x)
                    yield from backtrack(y+1, queens)
                    queens.pop()
                    
                    for occupiedY, occupiedX in myOccupied:
                        board[occupiedY][occupiedX] -= 1
        
        return list(backtrack(0, []))

Edited on 05/22/2021. Simplify the method for caculating occupied positions.

Edited on 05/29/2021. Optimize performance by only marking poisition on right and on rows below.

[LeetCode] 47. Permutations II

Problem : https://leetcode.com/problems/permutations-ii/description/

This problem is similar to 46. Permutations

To avoid duplication, the input array needs to be sorted first.

So we avoid picking number with same value as the start number of permutation.

Instead of swapping numbers, we need to take out the selected number to keep the sorted order of original array.

Time Complexity = O(N * N!)

Space Complexity = O(N * N!)

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # sort to group number with same value together
        nums.sort()
        result = []
        
        def backtrack(tmp):
            if not nums:
            	# no more candidate number left
                if tmp:
                    result.append(partial)
                return
            
            for i in range(0, len(nums)):
                # skip number with same value to avoid duplicatation
                if i > 0 and nums[i] == nums[i-1]:
                    continue
                
                # take the selected number out of candidate array
                n = nums.pop(i)
                
                backtrack(tmp + [n])
                
                # restore candidate array
                nums.insert(i, n)
                
        backtrack([])
        return result

Use hash table to avoid duplicate permutation

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtrack(start):
            if start == len(nums):
                result.append(nums[:])
            else:
                seen = set()
                for i in range(start, len(nums)):
                    if nums[i] in seen:
                        continue
                    
                    seen.add(nums[i])
                    
                    nums[start], nums[i] = nums[i], nums[start]
                    backtrack(start + 1)
                    nums[start], nums[i] = nums[i], nums[start]
        
        backtrack(0)
        return result

A hash table backed backtracking approach.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        counter = Counter(nums)
        keys = counter.keys()
        
        def backtrack(tmp):
            if len(tmp) == len(nums):
                result.append(tmp)
            else:
                for k in keys:
                    if counter[k] == 0:
                        continue
                        
                    counter[k] -= 1
                    backtrack(tmp + [k])
                    counter[k] += 1
        
        backtrack([])
        return result

[LeetCode] 46. Permutations

Problem : https://leetcode.com/problems/permutations/description/

Use backtracking approach to find all combinations.

Let permutation[i] = permutation starts with nums[i],

nums[] - nums[i] = nums without nums[i]

permutation[i] = nums[i] + permutation( nums[] - nums[i] )

Time Complexity = O(n * n!)

Space Complexity = O(n * n!)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        if not nums: return []
        
        N = len(nums)
        result = []
        
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]
        
        def backtrack(start):
            if start == N:
                result.append(nums[:])
            else:
                for i in range(start, N):
                    swap(i, start)
                    backtrack(start+1)
                    swap(i, start)
        
        backtrack(0)
        return result

[LeetCode] 40. Combination Sum II

Problem :  https://leetcode.com/problems/combination-sum-ii/

Should sort the candidates array first and skip candidate which has same value as its previous one to avoid duplicate result

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        result = []
        L = len(candidates)
        candidates.sort()
        
        def backtracking(start, partial, n):
            if n == 0:
                if partial:
                    result.append(partial)
                    
            for i in range(start, L):
                if n - candidates[i] < 0:
                    break
                
                # skip candidates with same value to avoid duplicate result
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                
                backtracking(i + 1, partial + [candidates[i]], n - candidates[i])
            
        backtracking(0, [], target)
        
        return result