Permutations II

1. Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

2. Idea

This problem is almost identical to LeetCode – Permutations, except that numbers may be duplicated and that unique permutations are needed. So we can adopt a similar idea as in the earlier problem with minor modifications. For example, with the use of a boolean array, do not consider to add a duplicate number to the next recursion if its earlier appearance has not been considered yet. This will avoid duplicate permutations.

3. Implementation

4. Wrap-up

Pay attention to Line 19 and Line 34~37. Those are all the differences from its sibling problem.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s