Combination Sum

Medium

backtrackingrecursionarray

Given an array of distinct positive integers candidates and a target, return all unique combinations that sum to target. The same candidate may be used unlimited times.

Input

Line 1: space-separated candidates
Line 2: integer target

Output: one combination per line, elements in non-decreasing order. Print nothing if none exist.

Example 1

Input:

2 3 6 7
7

Output:

2 2 3
7

Example 2

Input:

2 3 5
8

Output:

2 2 2 2
2 3 3
3 5

Example 3

Input:

2
1

Output:

Constraints

1 ≤ candidates.length ≤ 30
2 ≤ candidates[i] ≤ 40, distinct
1 ≤ target ≤ 40

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Combination Sum

Medium

backtrackingrecursionarray

Given an array of distinct positive integers candidates and a target, return all unique combinations that sum to target. The same candidate may be used unlimited times.

Input

Line 1: space-separated candidates
Line 2: integer target

Output: one combination per line, elements in non-decreasing order. Print nothing if none exist.

Example 1

Input:

2 3 6 7
7

Output:

2 2 3
7

Example 2

Input:

2 3 5
8

Output:

2 2 2 2
2 3 3
3 5

Example 3

Input:

2
1

Output:

Constraints

1 ≤ candidates.length ≤ 30
2 ≤ candidates[i] ≤ 40, distinct
1 ≤ target ≤ 40

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.