# Deduplication - Backtracking / Dedup

This is the 3sum problem: - LeetCode

I am finding this pretty hard to follow. I think it could use some work in general. Here are a few of the things confusing me:

1. What must be unique? nums[i], or i? In the problem statement, you say both nums[i] and later i must be unique, but I donâ€™t think thatâ€™s what you mean.
2. Iâ€™m confused about the layout of this question. Usually, thereâ€™s a â€śtry it yourselfâ€ť code box, and then you reduce the problem back to the core concept of this section. That doesnâ€™t happen (but I think if you did this, the explanation would benefit).

To answer your first question: i, j, and k must be unique. That is, you cannot choose the same index twice (so if your target is 15, and nums is [5, 6, 7], you cannot choose (5, 5, 5) as your triplet). You can choose two elements that have the same value at different indices to be part of the same triplet (e.g. if nums is [-1, 0, 3, 5, -1, 2] you can have (-1, 3, -1) as one of your triplets, since you selected those values from indices 0, 2, and 4). The triplets themselves must also be unique from each other (e.g. you can not have the triplet (-1, 3, -1) twice).

+1 on the rewrite of this oneâ€¦ its a bit confusing. Also just saying you have 2sum, use it, is a strange place to start, maybe thereâ€™ s a better example to illustrate this topic?

The monotonic ordering example I didnâ€™t quite grasp. Why canelements be discounted entirely once used in the first triplet? You can reuse elements in other triplets. Maybe need to see a more complex example here.

actually the AI tutor explained it much betterâ€¦and the longer example was better to illustateâ€¦

"Sure! Letâ€™s consider the following example:

nums = [7, 2, 3, 4, 5, 7]
target = 12

Initially, the input `nums` is sorted to become [2, 3, 4, 5, 7, 7].

When we iterate over `nums` and reach `nums[0] = 2`, we consider all the subsets that contain 2 and sum up to the remaining amount 10. The possible subsets are:

• [2, 4, 4]
• [2, 3, 5]

Now, when we reach `nums[1] = 3`, we want to avoid using it with another 2. Since we already considered all the subsets including 2 during `nums[0] = 2`, using another 2 will produce duplicates. Therefore, we only consider subsets that contain 3 and sum up to the remaining amount 9. The possible subset is:

• [3, 3, 6]

Similarly, when we reach `nums[2] = 4`, we avoid using it with another 2 or 3. We already considered all the subsets including 2 and 3 during the previous iterations. So, we only consider subsets that contain 4 and sum up to the remaining amount 8. The possible subset is:

• [4, 4, 4]

Finally, when we reach `nums[3] = 5`, we avoid using it with 2, 3, or 4. We already considered all the subsets including these elements during the previous iterations. So, we only consider subsets that contain 5 and sum up to the remaining amount 7. The possible subset is:

• [5, 6, 7]

In this example, the monotonic-ordering output eliminates duplicates by only considering the elements that have not been fully-considered before. By avoiding the use of previously considered elements, we ensure that each triplet is unique and we eliminate duplicate combinations of numbers."

Iâ€™m not really getting why this problem and its analysis are listed under the category of backtrackingâ€¦

2 Likes

is this a mistake

• nums[0] = 3: call twoSum(nums, 3) = [1,2], result = `[3,1,2]`
shouldnt the call to twoSum be twoSum(nums, 0)

Why is this part of backtracking ? Seems like a combination of 2sum and some normal loop runs. What am I missing ?