Posts tagged as “permutation”

Shuffle a set of numbers without duplicates.

Example:

C++

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.  Return a list of all possible strings we could create.

Note:

• S will be a string with length at most 12.
• S will consist only of letters or digits.

Solution 1: DFS

Time complexity: O(n*2^l), l = # of letters in the string

Space complexity: O(n) + O(n*2^l)

Python 3

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Example 2:

Note:

• arr will have length in range [1, 10].
• arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

Java

Python3

Problem:

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.

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

Idea:

DFS

Solution: C++

Python