How to remove duplicates from a list of lists, having different orders

Question

This time I am working on Combination sum problem Leetcode. This is very interesting problem which goes like this.

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Source: Leetcode: Combination sum

For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is:

[[7],[2, 2, 3]]

Now, I have written the following algorithm which solves my purposes, almost. The problem is my algorithm doesn't remove the duplicates. Let me show you how:

 def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candies = []
        if target in candidates and len(candidates) ==1:
            return [[target]]
        for idx in range(len(candidates)):
            residual = target
            count =0
            while residual >= candidates[idx]:
                residual -= candidates[idx]
                if candidates[idx] == target:
                    candies.append([candidates[idx]])
                count += 1
                if (residual in candidates and (residual-candidates[idx]) <= candidates[idx]):
                    candies.append([candidates[idx]]*count+[residual])
        return candies

So we have a result list known as candies (short for candidates, super bad variable name but I was not dealing with the problem seriously, previously).

Steps:

The first if statement checks the base case if we have only one candidate and returns that as a list of list.
We iterate through the candidates, on each iteration we initialize the residual to target and count to zero. count help us track of how many times we repetitively call the same number and then create a list of lists at the end. [candidates[idx]]*count+[residual].
The final inner loop is a while loop which iterates until our residual is greater than or equal to the candidate[idx]. Thus taking each element from the candidates one at a time and check if the repetitively selecting the same element sums to target. Also, the 'if' statement adds any intermediate elements that are in the list and can become candies (result set).

Thus solving the problem partially. My problem is we get same combinations of elements. Here's how: input: [2,3,6,7,1] target = 3 we select 2 we repetitively select it until our residual (7) is below the 2, we choose 2 one time and then search and then choose 1. Giving us [2,1] but when it goes to 1 checks. and then choose 2 giving us [1,2] which is a duplicate combination. How can solve this problem? Any improvement that you may see?

@dawg Yes, yes I know the work around but what if we have such situation? (sets are much much efficient in python, I agree.) Can we find any other check before appending? — Slayer, Feb 07 '17 at 15:32
See this post about ordered sets in Python and consider implementing a simple membership test before appending new results: https://stackoverflow.com/questions/1653970/does-python-have-an-ordered-set — clockelliptic, Jul 15 '19 at 20:19

score 0 · Answer 1 · answered Jul 15 '19 at 20:17

Sort your successful subsets. Then, before appending a successful subset, check to see if it exists in your collection of successful candidate combinations.

# suppose your target = 3
old_combinations = [[1,2]]
new_combination = [2, 1]

if sorted(new_combination) not in old_combinations:
    old_combinations.append(sorted(new_combination))
    print("found a unique combo!")
else:
    pass

How to remove duplicates from a list of lists, having different orders

1 Answers1