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:
- 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.
- 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…
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)