Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

491. Increasing Subsequences #86

Open
tech-cow opened this issue Feb 11, 2020 · 0 comments
Open

491. Increasing Subsequences #86

tech-cow opened this issue Feb 11, 2020 · 0 comments

Comments

@tech-cow
Copy link
Owner

tech-cow commented Feb 11, 2020

第一刷

'''
Bug 1: 这里如果 == base case底端,很多过程中的case都不会被记录
if index == len(nums) and len(temp) >= 2:

疑问:
为什么会有[4,7,7]这个output,set不会把第二个7去重么?

答:
每层递归的都会开一次新的set,而不是globalSet。所以只会针对当前层的duplicate
比如arr = [4,7,7]
    arr[1]是第二层的
    arr[2]是第三层的,到达第三层的时候,新开辟的set里面不会有第二层的7
'''
    
class Solution(object):
    def findSubsequences(self, nums):
        res = []
        self.dfsHelper(nums, [], 0, res)
        return res
    
    
    def dfsHelper(self, nums, temp, index, res):
        # Bug 1
        if index <= len(nums) and len(temp) >= 2:
            res.append(temp[:])

        visited = set()
        for i in range(index, len(nums)):
            if temp and temp[-1] > nums[i]: continue
            if nums[i] in visited: continue
            visited.add(nums[i])
            
            temp.append(nums[i])
            self.dfsHelper(nums, temp, i + 1, res)
            temp.pop()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant