Создать комбинации подмножеств без дубликатов? - PullRequest
Новая
       32

Создать комбинации подмножеств без дубликатов?

0 голосов
/ 04 июля 2018

Учитывая список чисел, которые могут иметь повторяющиеся числа, вернуть все возможные комбинации подмножеств.

Если S = ​​[2,2,2], решение:

[[[2], [2], [2]], [[2], [2,2]], [[2, 2, 2]]]

--- На самом деле есть серия проблем, выше Split String III ---

Split String

Дайте строку, вы можете разделить строку после одного символа или двух соседних символов и сделать строку, состоящую только из одного символа или двух символов. Выведите все возможные результаты. 

Example
Given the string "123"
return [["1","2","3"],["12","3"],["1","23"]]

Split String II

Дайте строку, вы можете разделить строку после одного символа или любых соседних символов, и сделать строку из этих символов. Выведите все возможные результаты. 

Example
Given the string "123"
return [['1', '2', '3'], ['1', '23'], ['12', '3'], ['123']]

Split String III

Дайте строку, вы можете разделить строку после одного символа или любых соседних символов, и сделать строку из этих символов. Выведите все возможные результаты. Строка может содержать повторяющиеся числа, уменьшать дублированные результаты, сохранять их в лексикографическом порядке. 

Example
Given the string "222"
return [['2', '2', '2'], ['2', '22'], ['222']]

1 Ответ

0 голосов
/ 11 июля 2018

Получил ансер для ссылки, используйте расщепление как метку, чтобы уменьшить дублирующиеся dfs. 

   def subsets4(self, S):
        res = []
        split = [False for _ in range(len(S))]
        split_num = {}
        self.count = 0 
        def dfs(start_index, tmp):
            self.count += 1 
            if start_index == len(S):
                res.append(tmp)
                return 
            for i in range(start_index,len(S)):
                if (i >=2 and S[i-1] == S[i] and split[i-2] == False and split_num[S[i]] != False):
                    continue
                split[i] = True
                if S[start_index] == S[i]:
                    split_num[S[i]] = True
                dfs(i + 1, tmp + [S[start_index:i+1]])
                split_num[S[i]] = False
                split[i] = False
        S.sort()
        dfs(0, [])
        print 'dfs count:', self.count,
        return res 

>>> subsets4([2, 2, 2, 2, 2])
>>> dfs count: 20 [[[2], [2], [2], [2], [2]], [[2], [2], [2], [2, 2]], [[2], [2], [2, 2, 2]], [[2], [2, 2], [2, 2]], [[2], [2, 2, 2, 2]], [[2, 2], [2, 2, 2]], [[2, 2, 2], [2, 2]], [[2, 2, 2, 2, 2]]]

------------------ Также прикреплен разделенный ответ ---------------- 

Class Solution(object):


    def splitString(self, S):
        if s is None:
            return []

        res = []
        # dfs helper to search solution for index + 1, index + 2
        def dfs(start, tmp):
            if start == len(S):
                res.append(tmp)
            end = min(start + 2, len(S))
            for i in range(start, end):
                dfs(i+1, tmp + [S[start:i+1]])

        dfs(0, [])
        return res


    def splitString2(self, S):
        if s is None:
            return []

        res = []
        # dfs helper to search solution for index + 1, index + 2
        def dfs(start, tmp):
            if start == len(S):
                res.append(tmp)
            end = len(S)
            for i in range(start, end):
                dfs(i+1, tmp + [S[start:i+1]])

        dfs(0, [])
        return res

    def splitString3(self, S):
        res = []
        split = [False for _ in range(len(S))]
        split_num = {}

        def dfs(start, tmp):
            if start == len(S):
                res.append(tmp)
                return 
            for i in range(start,len(S)):
                if (i >=2 and S[i-1] == S[i] and split[i-2] == False and split_num[S[i]] != False):
                    continue
                split[i] = True
                if S[start] == S[i]:
                    split_num[S[i]] = True
                dfs(i + 1, tmp + [S[start:i+1]])
                split_num[S[i]] = False
                split[i] = False

        dfs(0, [])
        return res
...