Leo-20181202.md

Leo Lei | 雷雨

Dec 02, 2018

Subset and sebsequence

Given a set of items, return all subsets of the set.

Below DFS-based solution is actually applying the Pascal's rule:

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for any natural number n we have

where is a binomial coefficient.

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

        return ans

path is an accumulator to get combinations of a given length (k)

It's not difficult to build a brute-force solution based on the subset solution for those subsequence-related problems, e.g. Longest Increasing Subsequence.

Essentially, subsequence is a subset of a string.

class Solution:
    max_len = 0
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def dfs(path, start):
            self.max_len = max(self.max_len, len(path))
            for i in range(start, len(nums)):
                if (path and nums[i] > path[-1]) or not path:
                    dfs(path+[nums[i]], i+1)
                             
        dfs([], 0)

        return self.max_len

We just need to set the condition where the traversal should go deeper.

Combination

Similarly, combination problem is a subset problem with additional constraint on the output length.

class Solution:
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        def dfs(res, start, curr):
            if len(curr) == k:
                res.append(curr)
            elif len(curr) < k:
                for i in range(start, n):
                    num = i+1
                    dfs(res, i+1, curr+[num])
        
        res = []
        dfs(res, 0, [])
        
        return res

Permutation

Given a list of items, return all permutations

Order matters for permutation, thus the ways of picking k from n to form permutations is greater than the ways to form combinations of the same length. Thinking both as graph problems, permutation is like a fully connected undirected graph - every node connects to every other nodes. Thus, just like traversing a graph, a way to mark the visited nodes is needed.

Permutations

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(res, curr, visited):
            if len(curr) == len(nums):
                res.append(curr)
            else:
                for i, num in enumerate(nums):
                    if not visited[i]:
                        visited[i] = True
                        dfs(res, curr+[num], visited)
                        visited[i] = False
        
        res = []
        visited = [False for _ in nums]
        dfs(res, [], visited)
        
        return res

Combination is more like a tree - a root points to its children which point to their children. The output depends on the process of forming the graph. For example, {1, 2, 3} is same as {2, 3, 1} , from the perspective of combination. Like traversing a tree, there is no need to mark what have been visited.