Solve Two Backtracking Array Problems

You will solve two independent coding problems. For each problem, first discuss edge cases, then implement a correct solution, and finally explain how you would optimize it.

Problem 1: Find Three Cards Summing to 15

You are given a list of integer card values. Return the indices of any three distinct cards whose values sum to exactly 15. If no such three cards exist, return an empty result.

Requirements:

• Each card may be used at most once.
• The input may contain duplicate values.
• The returned indices must be distinct.
• Discuss a brute-force approach and an optimized approach.

Example:

cards = [2, 7, 4, 8, 6, 1]

A valid answer is indices for values 7 + 6 + 2 = 15.

Problem 2: Maximize Unique Characters from a Word List

You are given a list of lowercase words. Choose any subset of the words and concatenate them in any order. The final concatenated string must contain no repeated characters. Return the maximum possible length of such a concatenation.

Requirements:

• A word that contains duplicate characters internally cannot be used.
• Each word may be chosen at most once.
• Return only the maximum length, not the actual subset.
• Discuss a straightforward backtracking solution and at least one optimization.

Example:

words = ["ab", "cd", "aef", "gh"]

One valid choice is "cd" + "aef" + "gh", which has length 7 and all unique characters.

Part 1: Find Three Cards Summing to 15

Given a list of integer card values, return the indices of three distinct cards whose values add up to exactly 15. If multiple valid triples exist, return the lexicographically smallest triple of indices in increasing order. If no such triple exists, return an empty list.

A brute-force approach checks every triple of indices in O(n^3). A better solution should improve on that.

Constraints

• 0 <= len(cards) <= 2000
• -10^9 <= cards[i] <= 10^9
• Indices in the answer must be distinct
• Duplicate card values may appear

Examples

Example 1

Input: ([2, 7, 4, 8, 6, 1],)
Output: [0, 1, 4]

Explanation: Values at indices 0, 1, and 4 are 2, 7, and 6, which sum to 15.

Example 2

Input: ([5, 5, 5, 5],)
Output: [0, 1, 2]

Explanation: There are multiple valid triples, so return the lexicographically smallest one.

Hints

1. Try fixing the first two indices and asking what third value is needed to reach 15.
2. To make the answer deterministic, scan i and j from left to right and choose the earliest valid k > j.

Part 2: Maximize Unique Characters from a Word List

You are given a list of lowercase words. Choose any subset of the words and concatenate them in any order so that the final string contains no repeated characters. Return the maximum possible length of such a concatenation.

A word that contains duplicate characters internally cannot be used at all. A straightforward solution uses backtracking over subsets. An optimized solution can represent each word as a bitmask and prune impossible branches.

Constraints

• 0 <= len(words) <= 16
• 1 <= len(words[i]) <= 26
• words[i] contains only lowercase English letters

Examples

Example 1

Input: (['ab', 'cd', 'aef', 'gh'],)
Output: 7

Explanation: One best choice is 'cd' + 'aef' + 'gh', which has length 7 and all unique characters.

Example 2

Input: ([],)
Output: 0

Explanation: Edge case: choosing nothing gives length 0.

Hints

1. First discard any word that already contains a repeated character inside itself.
2. Represent each valid word as a 26-bit mask so overlap checks become very fast.