"""
# LC 39: Combination Sum

Given an array of distinct integers `candidates` and a target integer `target`, return
a list of all unique combinations of candidates where the chosen numbers sum to target.
The same number may be chosen an unlimited number of times. Two combinations are unique
if the frequency of at least one chosen number differs.

## Examples
```text
Input:  candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]

Input:  candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Input:  candidates = [2], target = 1
Output: []
```

## Constraints
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- All elements of candidates are distinct.
- 1 <= target <= 40
"""
from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        """
        ## 39. Combination Sum

        Given an array of distinct integers candidates and a target integer target,
        return a list of all unique combinations of candidates where the chosen numbers
        sum to target. You may return the combinations in any order.

        The same number may be chosen from candidates an unlimited number of times.
        Two combinations are unique if the frequency of at least one of the chosen
        numbers is different.

        ### Examples

        ```text
        Input:  candidates = [2, 3, 6, 7], target = 7
        Output: [[2, 2, 3], [7]]

        Input:  candidates = [2, 3, 5], target = 8
        Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

        Input:  candidates = [2], target = 1
        Output: []
        ```

        ### Constraints
        - `1 <= candidates.length <= 30`
        - `2 <= candidates[i] <= 40`
        - All elements of candidates are distinct.
        - `1 <= target <= 40`
        """
        # Candidates can be reused: recurse with same index i
        # Prune when remaining < 0; record when remaining == 0
        # O(n^(t/m)) time where t=target, m=min candidate; O(t/m) stack space
        candidates.sort()
        result = []

        def bt(start, remaining, current):
            if remaining == 0:
                result.append(current[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break
                current.append(candidates[i])
                bt(i, remaining - candidates[i], current)
                current.pop()

        bt(0, target, [])
        return result


if __name__ == '__main__':
    s = Solution()
    assert sorted(s.combinationSum([2, 3, 6, 7], 7)) == sorted([[2, 2, 3], [7]])
    assert sorted(s.combinationSum([2, 3, 5], 8)) == sorted([[2, 2, 2, 2], [2, 3, 3], [3, 5]])
    assert s.combinationSum([2], 1) == []
    print("All tests passed.")

"""
# LC 40: Combination Sum II

Given a collection of candidate numbers (which may contain duplicates) and a target
number, find all unique combinations where the candidates sum to target. Each number
may be used at most once, and the solution set must not contain duplicate combinations.

## Examples
```text
Input:  candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Input:  candidates = [2, 5, 2, 1, 2], target = 5
Output: [[1, 2, 2], [5]]
```

## Constraints
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
"""
from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        """
        ## 40. Combination Sum II

        Given a collection of candidate numbers (candidates) and a target number (target),
        find all unique combinations in candidates where the candidate numbers sum to target.

        Each number in candidates may only be used once in the combination.
        Note: The solution set must not contain duplicate combinations.

        ### Examples

        ```text
        Input:  candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
        Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

        Input:  candidates = [2, 5, 2, 1, 2], target = 5
        Output: [[1, 2, 2], [5]]
        ```

        ### Constraints
        - `1 <= candidates.length <= 100`
        - `1 <= candidates[i] <= 50`
        - `1 <= target <= 30`
        """
        # Sort so duplicates are adjacent; skip duplicate values at same level
        # Each candidate used at most once: recurse with i+1
        # O(2^n) time, O(n) stack space
        candidates.sort()
        result = []

        def bt(start, remaining, current):
            if remaining == 0:
                result.append(current[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                current.append(candidates[i])
                bt(i + 1, remaining - candidates[i], current)
                current.pop()

        bt(0, target, [])
        return result


if __name__ == '__main__':
    s = Solution()
    assert sorted(s.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8)) == sorted([[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]])
    assert sorted(s.combinationSum2([2, 5, 2, 1, 2], 5)) == sorted([[1, 2, 2], [5]])
    print("All tests passed.")

"""
LC 216 - Combination Sum III

Problem: Find all combinations of exactly k numbers from 1-9 that sum to n.
Each number may be used at most once.

Examples:
    k=3, n=7  -> [[1,2,4]]
    k=3, n=9  -> [[1,2,6],[1,3,5],[2,3,4]]

Constraints:
    2 <= k <= 9
    1 <= n <= 60

Approach: Backtracking O(C(9,k)) — pick from 1-9 in increasing order,
    prune branch when current sum exceeds n or remaining slots can't be filled.
"""

from typing import List


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []

        def backtrack(start: int, combo: List[int], remaining: int) -> None:
            # Found valid combination of exactly k numbers summing to n
            if len(combo) == k and remaining == 0:
                result.append(combo[:])
                return
            # Prune: too many numbers already, or impossible to reach sum
            if len(combo) == k or remaining < 0:
                return
            for num in range(start, 10):
                combo.append(num)
                backtrack(num + 1, combo, remaining - num)  # no reuse: start = num+1
                combo.pop()

        backtrack(1, [], n)
        return result


if __name__ == '__main__':
    sol = Solution()
    assert sol.combinationSum3(3, 7) == [[1, 2, 4]]
    assert sol.combinationSum3(3, 9) == [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
    assert sol.combinationSum3(4, 1) == []
    print("All tests passed.")

"""
# LC 77: Combinations

Given two integers `n` and `k`, return all possible combinations of `k` numbers chosen
from the range `[1, n]`. The answer may be returned in any order.

## Examples
```text
Input:  n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Input:  n = 1, k = 1
Output: [[1]]
```

## Constraints
- 1 <= n <= 20
- 1 <= k <= n
"""
from typing import List


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        """
        ## 77. Combinations

        Given two integers n and k, return all possible combinations of k numbers
        chosen from the range [1, n]. You may return the answer in any order.

        ### Examples

        ```text
        Input:  n = 4, k = 2
        Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

        Input:  n = 1, k = 1
        Output: [[1]]
        ```

        ### Constraints
        - `1 <= n <= 20`
        - `1 <= k <= n`
        """
        # Choose k numbers from [1..n]; start from 'start' to avoid duplicates
        # Prune: if remaining numbers < k - len(path), can't complete — stop early
        # O(C(n,k) * k) time, O(k) stack space
        result = []

        def bt(start, current):
            if len(current) == k:
                result.append(current[:])
                return
            # prune: need at least (k - len(current)) more numbers
            for i in range(start, n - (k - len(current)) + 2):
                current.append(i)
                bt(i + 1, current)
                current.pop()

        bt(1, [])
        return result


if __name__ == '__main__':
    s = Solution()
    assert sorted(s.combine(4, 2)) == sorted([[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
    assert s.combine(1, 1) == [[1]]
    print("All tests passed.")

"""
# LC 282: Expression Add Operators

Given a string of digits and a target value, add binary operators (+, -, *)
between the digits to make the expression evaluate to the target.
Return all valid expressions.

## Examples

```text
Input:  num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Input:  num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Input:  num = "3456237490", target = 9191
Output: []
```

## Constraints
- 1 <= num.length <= 10
- num consists of only digits
- -2^31 <= target <= 2^31 - 1
"""
from typing import List


class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        # Backtracking: at each position, choose how many digits to take as operand
        # Track: current expression string, running total, previous operand (for * precedence)
        # Key insight for multiplication: undo previous addition, apply multiply
        #   e.g., "2+3*4" = (2+3) then *4 → need to undo +3: (5-3) + (3*4) = 14
        result = []

        def backtrack(idx, expr, total, prev):
            # Base case: used all digits
            if idx == len(num):
                if total == target:
                    result.append(expr)
                return

            # Try all possible operands starting at idx
            for i in range(idx, len(num)):
                # No leading zeros (except "0" itself)
                if i > idx and num[idx] == '0':
                    break

                curr_str = num[idx:i + 1]
                curr_val = int(curr_str)

                if idx == 0:
                    # First number: no operator before it
                    backtrack(i + 1, curr_str, curr_val, curr_val)
                else:
                    # Try +
                    backtrack(i + 1, expr + '+' + curr_str,
                              total + curr_val, curr_val)
                    # Try -
                    backtrack(i + 1, expr + '-' + curr_str,
                              total - curr_val, -curr_val)
                    # Try * (undo prev, apply prev*curr)
                    backtrack(i + 1, expr + '*' + curr_str,
                              total - prev + prev * curr_val, prev * curr_val)

        backtrack(0, "", 0, 0)
        return result


if __name__ == "__main__":
    sol = Solution()
    print(sol.addOperators("123", 6))    # ["1+2+3", "1*2*3"]
    print(sol.addOperators("232", 8))    # ["2*3+2", "2+3*2"]
    print(sol.addOperators("105", 5))    # ["1*0+5", "10-5"]

"""
# LC 22: Generate Parentheses

Given `n` pairs of parentheses, generate all combinations of well-formed parentheses.

## Examples
```text
Input:  n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Input:  n = 1
Output: ["()"]
```

## Constraints
- 1 <= n <= 8
"""
from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        """
        ## 22. Generate Parentheses

        Given n pairs of parentheses, write a function to generate all combinations
        of well-formed parentheses.

        ### Examples

        ```text
        Input:  n = 3
        Output: ["((()))","(()())","(())()","()(())","()()()"]

        Input:  n = 1
        Output: ["()"]
        ```

        ### Constraints
        - `1 <= n <= 8`
        """
        # Add '(' if open count < n; add ')' if close count < open count
        # Valid string when both counts reach n
        # O(4^n / sqrt(n)) time (Catalan number), O(n) stack space
        result = []

        def bt(current, open_count, close_count):
            if len(current) == 2 * n:
                result.append(current)
                return
            if open_count < n:
                bt(current + '(', open_count + 1, close_count)
            if close_count < open_count:
                bt(current + ')', open_count, close_count + 1)

        bt('', 0, 0)
        return result


if __name__ == '__main__':
    s = Solution()
    assert sorted(s.generateParenthesis(3)) == sorted(["((()))", "(()())", "(())()", "()(())", "()()()"])
    assert s.generateParenthesis(1) == ["()"]
    print("All tests passed.")

"""
# LC 17: Letter Combinations of a Phone Number

Given a string containing digits from 2-9, return all possible letter combinations that
the number could represent, using the standard telephone keypad mapping. Answer may be
returned in any order.

## Examples
```text
Input:  digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Input:  digits = ""
Output: []

Input:  digits = "2"
Output: ["a","b","c"]
```

## Constraints
- 0 <= digits.length <= 4
- digits[i] is a digit in the range ['2', '9'].
"""
from typing import List
from collections import deque


class Solution:
    PHONE = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }

    def letterCombinations_bt(self, digits: str) -> List[str]:
        """
        ## 17. Letter Combinations of a Phone Number

        Given a string containing digits from 2-9 inclusive, return all possible letter
        combinations that the number could represent. Return the answer in any order.

        A mapping of digits to letters (just like on the telephone buttons) is given below.
        Note that 1 does not map to any letters.

        ### Examples

        ```text
        Input:  digits = "23"
        Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

        Input:  digits = ""
        Output: []

        Input:  digits = "2"
        Output: ["a","b","c"]
        ```

        ### Constraints
        - `0 <= digits.length <= 4`
        - `digits[i]` is a digit in the range `['2', '9']`.
        """
        # O(4^n * n) time, O(n) stack space
        if not digits:
            return []
        result = []

        def bt(idx, current):
            if idx == len(digits):
                result.append(current)
                return
            for ch in self.PHONE[digits[idx]]:
                bt(idx + 1, current + ch)

        bt(0, '')
        return result

    def letterCombinations(self, digits: str) -> List[str]:
        """Iterative BFS: expand combinations level by level."""
        # Map each digit to its letters; DFS appending one letter per digit
        # Add to result when path length equals number of digits
        # O(4^n * n) time, O(4^n) space
        if not digits:
            return []
        queue = deque([''])
        for digit in digits:
            for _ in range(len(queue)):
                prefix = queue.popleft()
                for ch in self.PHONE[digit]:
                    queue.append(prefix + ch)
        return list(queue)


if __name__ == '__main__':
    s = Solution()
    expected = sorted(["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"])
    for fn in (s.letterCombinations_bt, s.letterCombinations):
        assert sorted(fn("23")) == expected
        assert fn("") == []
        assert sorted(fn("2")) == ["a", "b", "c"]
    print("All tests passed.")

"""
# M Coloring Problem

Given an undirected graph and m colors, determine if the graph can be colored
with at most m colors such that no two adjacent vertices share the same color.

## Examples

```text
Input:  n=4, edges=[[0,1],[1,2],[2,3],[3,0],[0,2]], m=3
Output: True

Input:  n=3, edges=[[0,1],[1,2],[0,2]], m=2
Output: False (triangle needs 3 colors)
```

## Constraints
- 1 <= n <= 20
- 1 <= m <= n
"""
from typing import List


class Solution:
    def graphColoring(self, n: int, edges: List[List[int]], m: int) -> bool:
        # Build adjacency list
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # color[i] = color assigned to node i (0 = uncolored)
        color = [0] * n

        def is_safe(node, c):
            # Check if assigning color c to node is valid
            # No adjacent node should have the same color
            for neighbor in graph[node]:
                if color[neighbor] == c:
                    return False
            return True

        def backtrack(node):
            # All nodes colored successfully
            if node == n:
                return True

            # Try each color 1..m for current node
            for c in range(1, m + 1):
                if is_safe(node, c):
                    color[node] = c
                    if backtrack(node + 1):
                        return True
                    color[node] = 0  # Backtrack
            return False

        return backtrack(0)


if __name__ == "__main__":
    sol = Solution()
    print(sol.graphColoring(4, [[0,1],[1,2],[2,3],[3,0],[0,2]], 3))  # True
    print(sol.graphColoring(3, [[0,1],[1,2],[0,2]], 2))              # False

"""
# LC 473: Matchsticks to Square

Given an array `matchsticks` of stick lengths, determine whether you can use every
matchstick exactly once to form a square (each of the four sides equal in length).
You may not break any stick. Return true if a square can be formed, otherwise false.

## Examples
```text
Input:  matchsticks = [1, 1, 2, 2, 2]
Output: true

Input:  matchsticks = [3, 3, 3, 3, 4]
Output: false
```

## Constraints
- 1 <= matchsticks.length <= 15
- 1 <= matchsticks[i] <= 10^8
"""
from typing import List


class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        """
        ## 473. Matchsticks to Square

        You are given an integer array matchsticks where matchsticks[i] is the length of
        the ith matchstick. You want to use all the matchsticks to make one square. You
        should not break any stick, but you can link them up, and each matchstick must be
        used exactly one time.

        Return true if you can make this square and false otherwise.

        ### Examples

        ```text
        Input:  matchsticks = [1, 1, 2, 2, 2]
        Output: true
        Explanation: 1+2=3, 1+2=3, 2=2... wait, side = 8/4 = 2. [2],[2],[2],[1,1] -> true

        Input:  matchsticks = [3, 3, 3, 3, 4]
        Output: false
        ```

        ### Constraints
        - `1 <= matchsticks.length <= 15`
        - `1 <= matchsticks[i] <= 10^8`
        """
        # Special case of partition into 4 equal subsets (k=4)
        # Sort descending for better pruning; skip duplicate bucket sums
        # O(4^n) time, O(n) stack space
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        side = total // 4
        matchsticks.sort(reverse=True)
        if matchsticks[0] > side:
            return False
        sides = [0] * 4

        def bt(idx):
            if idx == len(matchsticks):
                return sides[0] == sides[1] == sides[2] == side
            for i in range(4):
                if sides[i] + matchsticks[idx] <= side:
                    sides[i] += matchsticks[idx]
                    if bt(idx + 1):
                        return True
                    sides[i] -= matchsticks[idx]
                    if sides[i] == 0:
                        break  # prune symmetric branches
            return False

        return bt(0)


if __name__ == '__main__':
    s = Solution()
    assert s.makesquare([1, 1, 2, 2, 2]) is True
    assert s.makesquare([3, 3, 3, 3, 4]) is False
    assert s.makesquare([1, 1, 1, 1]) is True
    print("All tests passed.")

"""
# LC 51: N-Queens

The n-queens puzzle is the problem of placing `n` queens on an `n x n` chessboard so
that no two queens attack each other. Given an integer `n`, return all distinct
solutions. Each solution is a board configuration where 'Q' marks a queen and '.'
marks an empty cell.

## Examples
```text
Input:  n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Input:  n = 1
Output: [["Q"]]
```

## Constraints
- 1 <= n <= 9
"""
from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
        ## 51. N-Queens

        The n-queens puzzle is the problem of placing n queens on an n x n chessboard
        such that no two queens attack each other.

        Given an integer n, return all distinct solutions to the n-queens puzzle.
        You may return the answer in any order.

        Each solution contains a distinct board configuration of the n-queens' placement,
        where 'Q' and '.' both indicate a queen and an empty space, respectively.

        ### Examples

        ```text
        Input:  n = 4
        Output: [[".Q..","...Q","Q...","..Q."],
                 ["..Q.","Q...","...Q",".Q.."]]

        Input:  n = 1
        Output: [["Q"]]
        ```

        ### Constraints
        - `1 <= n <= 9`
        """
        # Place one queen per row; track occupied columns, diagonals, anti-diagonals
        # Backtrack by removing queen and clearing its column/diagonal markers
        # O(n!) time, O(n) space for tracking sets
        result = []
        cols, diag1, diag2 = set(), set(), set()
        board = [['.' ] * n for _ in range(n)]

        def bt(row):
            if row == n:
                result.append([''.join(r) for r in board])
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col); diag1.add(row - col); diag2.add(row + col)
                board[row][col] = 'Q'
                bt(row + 1)
                board[row][col] = '.'
                cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

        bt(0)
        return result


if __name__ == '__main__':
    s = Solution()
    res4 = s.solveNQueens(4)
    assert len(res4) == 2
    assert sorted(res4) == sorted([[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]])
    assert s.solveNQueens(1) == [["Q"]]
    print("All tests passed.")

"""
# LC 52: N-Queens II

The n-queens puzzle is the problem of placing `n` queens on an `n x n` chessboard so
that no two queens attack each other. Given an integer `n`, return the number of
distinct solutions to the n-queens puzzle.

## Examples
```text
Input:  n = 4
Output: 2

Input:  n = 1
Output: 1
```

## Constraints
- 1 <= n <= 9
"""
class Solution:
    def totalNQueens(self, n: int) -> int:
        """
        ## 52. N-Queens II

        The n-queens puzzle is the problem of placing n queens on an n x n chessboard
        such that no two queens attack each other.

        Given an integer n, return the number of distinct solutions to the n-queens puzzle.

        ### Examples

        ```text
        Input:  n = 4
        Output: 2

        Input:  n = 1
        Output: 1
        ```

        ### Constraints
        - `1 <= n <= 9`
        """
        # Same as N-Queens but only count solutions, don't store board state
        # O(n!) time, O(n) space
        cols, diag1, diag2 = set(), set(), set()
        count = 0

        def bt(row):
            nonlocal count
            if row == n:
                count += 1
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col); diag1.add(row - col); diag2.add(row + col)
                bt(row + 1)
                cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

        bt(0)
        return count


if __name__ == '__main__':
    s = Solution()
    assert s.totalNQueens(4) == 2
    assert s.totalNQueens(1) == 1
    assert s.totalNQueens(8) == 92
    print("All tests passed.")

"""
# LC 131: Palindrome Partitioning

Given a string `s`, partition it such that every substring of the partition is a
palindrome. Return all possible palindrome partitionings of `s`.

## Examples
```text
Input:  s = "aab"
Output: [["a","a","b"],["aa","b"]]

Input:  s = "a"
Output: [["a"]]
```

## Constraints
- 1 <= s.length <= 16
- s contains only lowercase English letters.
"""
from typing import List


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        """
        ## 131. Palindrome Partitioning

        Given a string s, partition s such that every substring of the partition is a
        palindrome. Return all possible palindrome partitioning of s.

        ### Examples

        ```text
        Input:  s = "aab"
        Output: [["a","a","b"],["aa","b"]]

        Input:  s = "a"
        Output: [["a"]]
        ```

        ### Constraints
        - `1 <= s.length <= 16`
        - s consists only of lowercase English letters.
        """
        # Try every prefix of remaining string; if it's a palindrome, recurse on suffix
        # Add complete partition to result when entire string is consumed
        # O(n * 2^n) time, O(n) stack space
        result = []

        def is_palindrome(sub):
            return sub == sub[::-1]

        def bt(start, current):
            if start == len(s):
                result.append(current[:])
                return
            for end in range(start + 1, len(s) + 1):
                substr = s[start:end]
                if is_palindrome(substr):
                    current.append(substr)
                    bt(end, current)
                    current.pop()

        bt(0, [])
        return result


if __name__ == '__main__':
    s = Solution()
    assert sorted(s.partition("aab")) == sorted([["a", "a", "b"], ["aa", "b"]])
    assert s.partition("a") == [["a"]]
    print("All tests passed.")

"""
# LC 698: Partition to K Equal Sum Subsets

Given an integer array `nums` and an integer `k`, return true if it is possible to
divide the array into `k` non-empty subsets whose sums are all equal.

## Examples
```text
Input:  nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: true

Input:  nums = [1, 2, 3, 4], k = 3
Output: false
```

## Constraints
- 1 <= k <= nums.length <= 16
- 1 <= nums[i] <= 10^4
- The frequency of each element is in the range [1, 4].
"""
from typing import List


class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        """
        ## 698. Partition to K Equal Sum Subsets

        Given an integer array nums and an integer k, return true if it is possible to
        divide this array into k non-empty subsets whose sums are all equal.

        ### Examples

        ```text
        Input:  nums = [4, 3, 2, 3, 5, 2, 1], k = 4
        Output: true
        Explanation: (5), (1,4), (2,3), (2,3)

        Input:  nums = [1, 2, 3, 4], k = 3
        Output: false
        ```

        ### Constraints
        - `1 <= k <= nums.length <= 16`
        - `1 <= nums[i] <= 10^4`
        - The frequency of each element is in the range [1, 4].
        """
        # Try placing each unused number into one of k buckets
        # Skip bucket if it already has the same sum as a previous bucket (pruning)
        # Return True when all k buckets reach target sum
        # O(k * 2^n) time with bitmask memoization, O(2^n) space
        total = sum(nums)
        if total % k != 0:
            return False
        target = total // k
        nums.sort(reverse=True)
        if nums[0] > target:
            return False

        n = len(nums)
        memo = {}

        def bt(mask, current_sum):
            if mask == (1 << n) - 1:
                return True
            if mask in memo:
                return memo[mask]
            for i in range(n):
                if mask & (1 << i):
                    continue
                next_sum = current_sum + nums[i]
                if next_sum > target:
                    continue
                new_mask = mask | (1 << i)
                if bt(new_mask, next_sum % target):
                    memo[mask] = True
                    return True
            memo[mask] = False
            return False

        return bt(0, 0)


if __name__ == '__main__':
    s = Solution()
    assert s.canPartitionKSubsets([4, 3, 2, 3, 5, 2, 1], 4) is True
    assert s.canPartitionKSubsets([1, 2, 3, 4], 3) is False
    assert s.canPartitionKSubsets([2, 2, 2, 2], 2) is True
    print("All tests passed.")

"""
# LC 46: Permutations

Given an array `nums` of distinct integers, return all the possible permutations. The
answer may be returned in any order.

## Examples
```text
Input:  nums = [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input:  nums = [1]
Output: [[1]]
```

## Constraints
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
"""
from typing import List


class Solution:
    def permute_used(self, nums: List[int]) -> List[List[int]]:
        """
        ## 46. Permutations

        Given an array nums of distinct integers, return all the possible permutations.
        You can return the answer in any order.

        ### Examples

        ```text
        Input:  nums = [1, 2, 3]
        Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

        Input:  nums = [0, 1]
        Output: [[0,1],[1,0]]

        Input:  nums = [1]
        Output: [[1]]
        ```

        ### Constraints
        - `1 <= nums.length <= 6`
        - `-10 <= nums[i] <= 10`
        - All integers of nums are unique.
        """
        # O(n!) time, O(n) extra space for used set
        result = []
        used = [False] * len(nums)

        def bt(current):
            if len(current) == len(nums):
                result.append(current[:])
                return
            for i in range(len(nums)):
                if not used[i]:
                    used[i] = True
                    current.append(nums[i])
                    bt(current)
                    current.pop()
                    used[i] = False

        bt([])
        return result

    def permute(self, nums: List[int]) -> List[List[int]]:
        """Swap-based backtracking: swap element into current position."""
        # Swap current index with each subsequent index to generate permutations
        # Backtrack by swapping back after recursion
        # O(n!) time, O(1) extra space (in-place swaps)
        result = []

        def bt(start):
            if start == len(nums):
                result.append(nums[:])
                return
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                bt(start + 1)
                nums[start], nums[i] = nums[i], nums[start]

        bt(0)
        return result


if __name__ == '__main__':
    s = Solution()
    expected = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    for fn in (s.permute_used, s.permute):
        assert sorted(fn([1, 2, 3])) == sorted(expected)
        assert sorted(fn([0, 1])) == sorted([[0, 1], [1, 0]])
    print("All tests passed.")

"""
# LC 47: Permutations II

Given a collection of numbers `nums` that might contain duplicates, return all possible
unique permutations in any order.

## Examples
```text
Input:  nums = [1, 1, 2]
Output: [[1,1,2],[1,2,1],[2,1,1]]

Input:  nums = [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```

## Constraints
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
"""
from typing import List


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        ## 47. Permutations II

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

        ### Examples

        ```text
        Input:  nums = [1, 1, 2]
        Output: [[1,1,2],[1,2,1],[2,1,1]]

        Input:  nums = [1, 2, 3]
        Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
        ```

        ### Constraints
        - `1 <= nums.length <= 8`
        - `-10 <= nums[i] <= 10`
        """
        # Sort to group duplicates; use a 'used' array to track which elements are in current path
        # Skip duplicate: if nums[i]==nums[i-1] and nums[i-1] not used, skip to avoid duplicate permutations
        # O(n!) time, O(n) stack space
        nums.sort()
        result = []
        used = [False] * len(nums)

        def bt(current):
            if len(current) == len(nums):
                result.append(current[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                # skip duplicate: same value as previous, and previous not used in this path
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                current.append(nums[i])
                bt(current)
                current.pop()
                used[i] = False

        bt([])
        return result


if __name__ == '__main__':
    s = Solution()
    assert sorted(s.permuteUnique([1, 1, 2])) == sorted([[1, 1, 2], [1, 2, 1], [2, 1, 1]])
    assert len(s.permuteUnique([1, 2, 3])) == 6
    print("All tests passed.")

"""
# Rat in a Maze

Given an n×n maze where 1 = open cell and 0 = blocked cell, find all paths
from (0,0) to (n-1,n-1). The rat can move Down, Left, Right, Up.
Return paths as strings of directions in lexicographical order.

## Examples

```text
Input:  maze = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]
Output: ["DDRDRR","DRDDRR"]

Input:  maze = [[1,0],[1,1]]
Output: ["DR","RD"] — wait, (0,1) is blocked, so only "DR" isn't valid. Actually "DR" means down then right = (0,0)->(1,0)->(1,1) = valid
```

## Constraints
- 2 <= n <= 5
- maze[0][0] == 1 and maze[n-1][n-1] == 1
"""
from typing import List


class Solution:
    def findPaths(self, maze: List[List[int]]) -> List[str]:
        # Backtracking: try all 4 directions (D,L,R,U in sorted order for lex output)
        # Mark cell visited before exploring, unmark on backtrack
        # Base case: reached (n-1, n-1) → add path to result
        n = len(maze)
        result = []
        visited = [[False] * n for _ in range(n)]

        def backtrack(r, c, path):
            # Reached destination
            if r == n - 1 and c == n - 1:
                result.append(path)
                return

            # Try D, L, R, U (lexicographic order)
            for dr, dc, d in [(1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R'), (-1, 0, 'U')]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1 and not visited[nr][nc]:
                    visited[nr][nc] = True
                    backtrack(nr, nc, path + d)
                    visited[nr][nc] = False  # Backtrack

        if maze[0][0] == 1:
            visited[0][0] = True
            backtrack(0, 0, "")
        return result


if __name__ == "__main__":
    sol = Solution()
    print(sol.findPaths([[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]))
    # Expected: ["DDRDRR", "DRDDRR"]

"""
# LC 78: Subsets

Given an integer array `nums` of unique elements, return all possible subsets (the power
set). The solution set must not contain duplicate subsets and may be returned in any
order.

## Examples
```text
Input:  nums = [1, 2, 3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Input:  nums = [0]
Output: [[],[0]]
```

## Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All the numbers of nums are unique.
"""
from typing import List


class Solution:
    def subsets_iterative(self, nums: List[int]) -> List[List[int]]:
        """
        ## 78. Subsets

        Given an integer array nums of unique elements, return all possible subsets
        (the power set). The solution set must not contain duplicate subsets.
        Return the solution in any order.

        ### Examples

        ```text
        Input:  nums = [1, 2, 3]
        Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

        Input:  nums = [0]
        Output: [[], [0]]
        ```

        ### Constraints
        - `1 <= nums.length <= 10`
        - `-10 <= nums[i] <= 10`
        - All integers in nums are unique.
        """
        # O(2^n) time, O(2^n) space
        result = [[]]
        for num in nums:
            result += [subset + [num] for subset in result]
        return result

    def subsets(self, nums: List[int]) -> List[List[int]]:
        """Backtracking: build subsets by choosing to include or skip each element."""
        # At each index, branch: include nums[i] or skip it
        # Leaf nodes (i == len(nums)) are complete subsets — add to result
        # O(2^n) time, O(n) stack space
        result = []

        def bt(start, current):
            result.append(current[:])
            for i in range(start, len(nums)):
                current.append(nums[i])
                bt(i + 1, current)
                current.pop()

        bt(0, [])
        return result


if __name__ == '__main__':
    s = Solution()
    for fn in (s.subsets_iterative, s.subsets):
        assert sorted(fn([1, 2, 3])) == sorted([[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]])
        assert sorted(fn([0])) == sorted([[], [0]])
    print("All tests passed.")

"""
# LC 90: Subsets II

Given an integer array `nums` that may contain duplicates, return all possible subsets
(the power set). The solution set must not contain duplicate subsets and may be returned
in any order.

## Examples
```text
Input:  nums = [1, 2, 2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Input:  nums = [0]
Output: [[],[0]]
```

## Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
"""
from typing import List


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
        ## 90. Subsets II

        Given an integer array nums that may contain duplicates, return all possible
        subsets (the power set). The solution set must not contain duplicate subsets.
        Return the solution in any order.

        ### Examples

        ```text
        Input:  nums = [1, 2, 2]
        Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]

        Input:  nums = [0]
        Output: [[], [0]]
        ```

        ### Constraints
        - `1 <= nums.length <= 10`
        - `-10 <= nums[i] <= 10`
        """
        # Sort first so duplicates are adjacent and easy to skip
        # Skip duplicate values at the same recursion level to avoid duplicate subsets
        # O(2^n) time, O(n) stack space
        nums.sort()
        result = []

        def bt(start, current):
            result.append(current[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                current.append(nums[i])
                bt(i + 1, current)
                current.pop()

        bt(0, [])
        return result


if __name__ == '__main__':
    s = Solution()
    assert sorted(s.subsetsWithDup([1, 2, 2])) == sorted([[], [1], [1, 2], [1, 2, 2], [2], [2, 2]])
    assert sorted(s.subsetsWithDup([0])) == sorted([[], [0]])
    print("All tests passed.")

"""
# LC 37: Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Each row, column, and 3×3 box must contain digits 1-9 without repetition.

## Examples

```text
Input:  board with '.' for empty cells
Output: board filled with valid solution
```

## Constraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit or '.'
- Input board has exactly one solution
"""
from typing import List


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        # Backtracking: find empty cell, try digits 1-9, validate, recurse
        # Optimization: use sets for rows, cols, boxes for O(1) validity check

        # Pre-populate constraint sets
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for r in range(9):
            for c in range(9):
                if board[r][c] != '.':
                    d = board[r][c]
                    rows[r].add(d)
                    cols[c].add(d)
                    boxes[(r // 3) * 3 + c // 3].add(d)

        def backtrack(pos):
            # Find next empty cell starting from pos
            while pos < 81:
                r, c = divmod(pos, 9)
                if board[r][c] == '.':
                    break
                pos += 1
            else:
                return True  # All cells filled

            r, c = divmod(pos, 9)
            box_id = (r // 3) * 3 + c // 3

            for d in '123456789':
                if d not in rows[r] and d not in cols[c] and d not in boxes[box_id]:
                    # Place digit
                    board[r][c] = d
                    rows[r].add(d)
                    cols[c].add(d)
                    boxes[box_id].add(d)

                    if backtrack(pos + 1):
                        return True

                    # Backtrack: remove digit
                    board[r][c] = '.'
                    rows[r].remove(d)
                    cols[c].remove(d)
                    boxes[box_id].remove(d)

            return False

        backtrack(0)


if __name__ == "__main__":
    sol = Solution()
    board = [
        ["5","3",".",".","7",".",".",".","."],
        ["6",".",".","1","9","5",".",".","."],
        [".","9","8",".",".",".",".","6","."],
        ["8",".",".",".","6",".",".",".","3"],
        ["4",".",".","8",".","3",".",".","1"],
        ["7",".",".",".","2",".",".",".","6"],
        [".","6",".",".",".",".","2","8","."],
        [".",".",".","4","1","9",".",".","5"],
        [".",".",".",".","8",".",".","7","9"]
    ]
    sol.solveSudoku(board)
    for row in board:
        print(row)

"""
# LC 1863: Sum of All Subset XOR Totals

The XOR total of an array is the bitwise XOR of all its elements, or 0 if the array is
empty. Given an array `nums`, return the sum of all XOR totals for every subset of
`nums`. Subsets with the same elements at different indices are counted separately.

## Examples
```text
Input:  nums = [1, 3]
Output: 6
Explanation: subsets [], [1], [3], [1,3] have XOR totals 0, 1, 3, 2 -> sum = 6

Input:  nums = [5, 1, 6]
Output: 28
```

## Constraints
- 1 <= nums.length <= 12
- 1 <= nums[i] <= 20
"""
from typing import List


class Solution:
    def subsetXORSum_brute(self, nums: List[int]) -> int:
        """
        ## 1863. Sum of All Subset XOR Totals

        The XOR total of an array is defined as the XOR of all its elements, or 0 if the
        array is empty. Given an array nums, return the sum of all XOR totals for every
        subset of nums.

        ### Examples

        ```text
        Input:  nums = [1, 3]
        Output: 6
        Explanation: subsets -> [], [1], [3], [1,3]
                     XOR    ->  0,   1,   3,    2   => sum = 6

        Input:  nums = [5, 1, 6]
        Output: 28

        Input:  nums = [3, 4, 5, 6, 7, 8]
        Output: 480
        ```

        ### Constraints
        - `1 <= nums.length <= 12`
        - `1 <= nums[i] <= 20`
        """
        # O(2^n * n) time, O(n) space
        n = len(nums)
        total = 0
        for mask in range(1 << n):
            xor = 0
            for i in range(n):
                if mask & (1 << i):
                    xor ^= nums[i]
            total += xor
        return total

    def subsetXORSum(self, nums: List[int]) -> int:
        """Bit manipulation: OR all elements, multiply by 2^(n-1)."""
        # For each element, branch: include in XOR or skip
        # Sum XOR values of all subsets at leaf nodes
        # O(n) time, O(1) space
        or_all = 0
        for x in nums:
            or_all |= x
        return or_all * (1 << (len(nums) - 1))


if __name__ == '__main__':
    s = Solution()
    assert s.subsetXORSum([1, 3]) == 6
    assert s.subsetXORSum([5, 1, 6]) == 28
    assert s.subsetXORSum([3, 4, 5, 6, 7, 8]) == 480
    assert s.subsetXORSum_brute([1, 3]) == 6
    assert s.subsetXORSum_brute([5, 1, 6]) == 28
    print("All tests passed.")

"""
# LC 140: Word Break II

Given a string `s` and a dictionary of strings `wordDict`, add spaces in `s` to
construct a sentence where each word is a valid dictionary word. Return all such
possible sentences in any order. The same dictionary word may be reused.

## Examples
```text
Input:  s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Input:  s = "pineapplepenapple",
        wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
```

## Constraints
- 1 <= s.length <= 20
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 10
"""
from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        """
        ## 140. Word Break II

        Given a string s and a dictionary of strings wordDict, add spaces in s to
        construct a sentence where each word is a valid dictionary word. Return all
        such possible sentences in any order.

        Note that the same word in the dictionary may be reused multiple times in
        the segmentation.

        ### Examples

        ```text
        Input:  s = "catsanddog",
                wordDict = ["cat","cats","and","sand","dog"]
        Output: ["cats and dog","cat sand dog"]

        Input:  s = "pineapplepenapple",
                wordDict = ["apple","pen","applepen","pine","pineapple"]
        Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]

        Input:  s = "catsandog",
                wordDict = ["cats","dog","sand","and","cat"]
        Output: []
        ```

        ### Constraints
        - `1 <= s.length <= 20`
        - `1 <= wordDict.length <= 1000`
        - `1 <= wordDict[i].length <= 10`
        - s and wordDict[i] consist of only lowercase English letters.
        - All strings in wordDict are unique.
        """
        # DFS with memoization: at each position try all words that match
        # Cache results per start index to avoid recomputation
        # O(2^n) time worst case, O(n) memoization reduces repeated work; O(n) stack space
        word_set = set(wordDict)
        memo = {}

        def bt(start):
            if start in memo:
                return memo[start]
            if start == len(s):
                return ['']
            sentences = []
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word in word_set:
                    for rest in bt(end):
                        sentences.append(word + (' ' + rest if rest else ''))
            memo[start] = sentences
            return sentences

        return bt(0)


if __name__ == '__main__':
    s = Solution()
    assert sorted(s.wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"])) == sorted(["cats and dog", "cat sand dog"])
    assert sorted(s.wordBreak("pineapplepenapple", ["apple", "pen", "applepen", "pine", "pineapple"])) == sorted(["pine apple pen apple", "pineapple pen apple", "pine applepen apple"])
    assert s.wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]) == []
    print("All tests passed.")

"""
# LC 79: Word Search

Given an `m x n` grid of characters `board` and a string `word`, return true if `word`
exists in the grid. The word can be constructed from letters of sequentially adjacent
cells (horizontally or vertically neighboring), where the same cell may not be used
more than once.

## Examples
```text
Input:  board = [["A","B","C","E"],
                 ["S","F","C","S"],
                 ["A","D","E","E"]], word = "ABCCED"
Output: true

Input:  board = [["A","B","C","E"],
                 ["S","F","C","S"],
                 ["A","D","E","E"]], word = "ABCB"
Output: false
```

## Constraints
- m == board.length, n == board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
"""
from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        """
        ## 79. Word Search

        Given an m x n grid of characters board and a string word, return true if word
        exists in the grid. The word can be constructed from letters of sequentially
        adjacent cells, where adjacent cells are horizontally or vertically neighboring.
        The same letter cell may not be used more than once.

        ### Examples

        ```text
        Input:  board = [["A","B","C","E"],
                          ["S","F","C","S"],
                          ["A","D","E","E"]], word = "ABCCED"
        Output: true

        Input:  board = [["A","B","C","E"],
                          ["S","F","C","S"],
                          ["A","D","E","E"]], word = "SEE"
        Output: true

        Input:  board = [["A","B","C","E"],
                          ["S","F","C","S"],
                          ["A","D","E","E"]], word = "ABCB"
        Output: false
        ```

        ### Constraints
        - `m == board.length`, `n = board[i].length`
        - `1 <= m, n <= 6`
        - `1 <= word.length <= 15`
        - board and word consist of only lowercase and uppercase English letters.
        """
        # DFS from each cell matching word[0]; mark cell visited by modifying grid
        # Backtrack by restoring the cell after recursion
        # O(m * n * 4^L) time where L = len(word), O(L) stack space
        m, n = len(board), len(board[0])

        def dfs(r, c, idx):
            if idx == len(word):
                return True
            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[idx]:
                return False
            tmp, board[r][c] = board[r][c], '#'
            found = (dfs(r + 1, c, idx + 1) or dfs(r - 1, c, idx + 1) or
                     dfs(r, c + 1, idx + 1) or dfs(r, c - 1, idx + 1))
            board[r][c] = tmp
            return found

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False


if __name__ == '__main__':
    s = Solution()
    board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
    import copy
    assert s.exist(copy.deepcopy(board), "ABCCED") is True
    assert s.exist(copy.deepcopy(board), "SEE") is True
    assert s.exist(copy.deepcopy(board), "ABCB") is False
    print("All tests passed.")