Share my python codes


  • 0
    C
    class Solution(object):
        def findSubsequences(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            ans = []
            def DFS(ind, result):
                if len(result)>=2:
                    ans.append(result[:])
                    
                record = set()#line1
                for i in range(ind, len(nums)):
                    if (not result or nums[i]>=result[-1]) and (not nums[i] in record):#line2
                        record.add(nums[i])#line3
                        result.append(nums[i])
                        DFS(i+1, result)
                        result.pop()
            DFS(0, [])
            return ans
    

    Typical backtracing solution. The issue is to skip the duplicate item. At beginning tried the method here, but because the nums is not sorted, so it cannot pass the test case [1,2,1,1]. But I do not like the usage of set in the following codes. Finally, I came out the above solution. If there is any solution where set not used, it should be better.

    class Solution(object):
        def findSubsequences(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            ans = set()
            def DFS(ind, result):
                if len(result)>=2:
                    ans.add(tuple(result))
                
                for i in range(ind, len(nums)):
                    if not result or nums[i]>=result[-1]:
                        result.append(nums[i])
                        DFS(i+1, result)
                        result.pop()
            DFS(0, [])
            return map(list, ans)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.