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: ```text 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: ```text words = ["ab", "cd", "aef", "gh"] ``` One valid choice is `"cd" + "aef" + "gh"`, which has length `7` and all unique characters.