Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

There is a bug in your Leetcode-go 39 combination sum #288

Open
shiiaii opened this issue Aug 29, 2024 · 3 comments
Open

There is a bug in your Leetcode-go 39 combination sum #288

shiiaii opened this issue Aug 29, 2024 · 3 comments

Comments

@shiiaii
Copy link

shiiaii commented Aug 29, 2024

You code does not skip the duplicated combination.
You need to add skip duplicated combination . See below.

        if nums[i] > target  {
            break
        }
        // the following to skip the duplicated combination
        if (len(c)!=0 && nums[i] < c[len(c)-1]) {
            continue
        }
@haowan1015
Copy link

haowan1015 commented Aug 29, 2024 via email

@xiaokuer
Copy link

xiaokuer commented Aug 29, 2024 via email

@halfrost
Copy link
Owner

halfrost commented Sep 1, 2024

@shiiaii Hi, about deduplication mechanism:

  • Since in each recursive call the index only moves forward (i starts from index), even if there are duplicate numbers in the array, they will not result in duplicate combinations.
  • For example, for the array [2, 3, 6, 7] and the target value 7, the combination [2, 2, 3] will only be considered once when the loop reaches 2. Subsequent iterations will not consider [2, 3, 2] or [3, 2, 2], thus avoiding duplicate combinations.

You can try submitting my code and you will get the result of accept. This is a screenshot of the result I just submitted.

image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants