# Concatenated Divisibility
**Difficulty:** HARD
[External](https://leetcode.com/problems/concatenated-divisibility)
Canonical: https://scaleengineer.com/dsa/problems/concatenated-divisibility
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## Problem
You are given an array of positive integers `nums` and a positive integer `k`.

A permutation of `nums` is said to form a **divisible concatenation** if, when you _concatenate_ _the decimal representations_ of the numbers in the order specified by the permutation, the resulting number is **divisible by** `k`.

Return the **lexicographically smallest** permutation (when considered as a list of integers) that forms a **divisible concatenation**. If no such permutation exists, return an empty list.

**Example 1:**

**Input:** nums = \[3,12,45\], k = 5

**Output:** \[3,12,45\]

**Explanation:**

| Permutation   | Concatenated Value | Divisible by 5 |
| ------------- | ------------------ | -------------- |
| \[3, 12, 45\] | 31245              | Yes            |
| \[3, 45, 12\] | 34512              | No             |
| \[12, 3, 45\] | 12345              | Yes            |
| \[12, 45, 3\] | 12453              | No             |
| \[45, 3, 12\] | 45312              | No             |
| \[45, 12, 3\] | 45123              | No             |

The lexicographically smallest permutation that forms a divisible concatenation is `[3,12,45]`.

**Example 2:**

**Input:** nums = \[10,5\], k = 10

**Output:** \[5,10\]

**Explanation:**

| Permutation | Concatenated Value | Divisible by 10 |
| ----------- | ------------------ | --------------- |
| \[5, 10\]   | 510                | Yes             |
| \[10, 5\]   | 105                | No              |

The lexicographically smallest permutation that forms a divisible concatenation is `[5,10]`.

**Example 3:**

**Input:** nums = \[1,2,3\], k = 5

**Output:** \[\]

**Explanation:**

Since no permutation of `nums` forms a valid divisible concatenation, return an empty list.

**Constraints:**

* `1 <= nums.length <= 13`
* `1 <= nums[i] <= 105`
* `1 <= k <= 100`

# Approaches
## Backtracking Search
This approach improves upon a naive brute-force method by generating permutations in lexicographical order and stopping as soon as the first valid permutation is found. To achieve this, the input array `nums` is sorted first. A recursive backtracking function then explores possible permutations, prioritizing smaller numbers at each step, effectively pruning the search space once a solution is found.
**Time:** O(N! * N). In the worst-case scenario (no solution exists or the solution is the lexicographically largest permutation), the algorithm explores the entire permutation tree, which has N! leaves. Each path construction involves operations that take O(N) time in total. · **Space:** O(N), where N is the number of elements in `nums`. This space is used for the recursion stack and to store the current path.
**Pros:** Conceptually simpler than dynamic programming.; Finds the lexicographically smallest solution first, which can be fast if such a solution exists early in the search.; Uses minimal space compared to DP.
**Cons:** The time complexity is O(N!), which is too slow for the given constraints (N up to 13).; It will likely result in a 'Time Limit Exceeded' error on most platforms for larger N.
### Explanation
The key to finding the lexicographically smallest permutation is to make locally optimal choices: at each step of building the permutation, try to place the smallest available number. Sorting the `nums` array initially facilitates this.

We use a recursive function, say `backtrack(current_path, used_mask, current_rem)`, to build the permutation. The function iterates through the sorted `nums` array. For each unused number `nums[i]`, it adds it to the `current_path`, calculates the new remainder, and makes a recursive call. If a recursive call finds a valid complete permutation, it propagates the result up, and all further exploration is halted. This ensures that the first solution found is indeed the lexicographically smallest.

The remainder is calculated on the fly and passed down in the recursion. The base case is when the path length equals `N`; we check if `current_rem` is 0. If so, a solution is found.

To handle duplicate numbers in `nums` and avoid generating duplicate permutations, we add a check: if `nums[i]` is the same as `nums[i-1]` and `nums[i-1]` has not been used in the current path construction level, we skip `nums[i]`.

```java
class Solution {
    int[] nums;
    int k;
    long[] p10;
    List<Integer> result = null;

    public int[] concatenatedDivisibility(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        Arrays.sort(this.nums);
        
        this.p10 = new long[nums.length];
        for (int i = 0; i < nums.length; i++) {
            p10[i] = (long) Math.pow(10, String.valueOf(nums[i]).length());
        }

        backtrack(new ArrayList<>(), new boolean[nums.length], 0);
        
        if (result == null) {
            return new int[0];
        }
        return result.stream().mapToInt(i -> i).toArray();
    }

    private void backtrack(List<Integer> path, boolean[] used, long currentRem) {
        if (result != null) return; // Already found a solution

        if (path.size() == nums.length) {
            if (currentRem == 0) {
                result = new ArrayList<>(path);
            }
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            // Skip duplicates to generate unique permutations
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

            used[i] = true;
            path.add(nums[i]);
            
            long newRem = (currentRem * p10[i] + nums[i]) % k;
            backtrack(path, used, newRem);
            
            // Backtrack
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}
```
### Algorithm
- Sort the input `nums` array to facilitate finding the lexicographically smallest permutation.
- Use a recursive backtracking function to explore permutations. The function should maintain the current path (partial permutation), a bitmask or boolean array for used elements, and the remainder of the concatenated number so far.
- The function iterates through the sorted `nums`. For each unused number, it adds it to the path, updates the remainder, and makes a recursive call.
- To avoid duplicate permutations when `nums` has duplicate elements, if `nums[i] == nums[i-1]` and `nums[i-1]` has not been used at the current level of recursion, skip `nums[i]`.
- The base case for the recursion is when the path length equals `N`. If the final remainder is 0, a solution is found. Since we explore in lexicographical order, this first solution is the answer.
- If a solution is found, stop the search immediately and return the result. If the entire search space is explored without finding a solution, return an empty list.

## Dynamic Programming with Bitmasking
Given the small constraint on `N` (up to 13), this problem can be solved efficiently using dynamic programming with a bitmask. This approach avoids the factorial time complexity of backtracking by storing and reusing the results of subproblems. The state of our DP captures the subset of numbers used (via a bitmask) and the remainder of the concatenated number formed by a permutation of this subset.
**Time:** O(2^N * k * N + N log N). The DP state space is `2^N * k`. For each state, we iterate up to `N` times to decide the next number. Sorting the array takes an initial `O(N log N)`. · **Space:** O(2^N * k), where N is the length of `nums` and k is the divisor. This space is dominated by the memoization and parent tables.
**Pros:** Efficient enough to pass the given constraints.; Guaranteed to find the optimal (lexicographically smallest) solution.
**Cons:** More complex to understand and implement compared to a simple backtracking solution.; Requires significant memory for the memoization and parent tables, although it's feasible for the given constraints.
### Explanation
The core idea is to solve for subproblems and store their results to avoid re-computation. A subproblem can be defined as: "Is it possible to form a valid divisible concatenation using a specific subset of the remaining numbers, given the prefix has already produced a certain remainder?"

We define a function `solve(mask, rem)` which determines if a valid suffix can be formed from the numbers not yet included in `mask`, assuming the prefix has a remainder `rem`. To find the lexicographically smallest permutation, we first sort `nums`. Then, inside `solve`, we iterate through available numbers `nums[i]` in increasing order. The first one that leads to a valid complete permutation will guarantee that we are on the path to the lexicographically smallest solution.

We use two tables:
1.  `memo[mask][rem]`: Stores whether the state `(mask, rem)` can lead to a solution (1 for possible, -1 for impossible, 0 for not computed).
2.  `parent[mask][rem]`: Stores the index `i` of the number `nums[i]` that should be chosen next from state `(mask, rem)` to be on the optimal path.

After the `solve` function populates these tables, we can reconstruct the final permutation by starting from the initial state `(mask=0, rem=0)` and following the indices stored in the `parent` table.

```java
class Solution {
    int[] nums;
    int n;
    int k;
    long[] p10;
    int[][] memo; // 0: not computed, 1: possible, -1: impossible
    int[][] parent; // stores the index of the number chosen

    public int[] concatenatedDivisibility(int[] nums, int k) {
        this.n = nums.length;
        this.nums = nums;
        this.k = k;
        
        Arrays.sort(this.nums);

        this.p10 = new long[n];
        for (int i = 0; i < n; i++) {
            p10[i] = (long) Math.pow(10, String.valueOf(nums[i]).length());
        }

        this.memo = new int[1 << n][k];
        this.parent = new int[1 << n][k];

        if (solve(0, 0) == -1) {
            return new int[0];
        }

        // Reconstruct path
        int[] result = new int[n];
        int currentMask = 0;
        int currentRem = 0;
        for (int i = 0; i < n; i++) {
            int index = parent[currentMask][currentRem];
            result[i] = this.nums[index];
            currentRem = (int) ((currentRem * p10[index] + this.nums[index]) % k);
            currentMask |= (1 << index);
        }
        return result;
    }

    private int solve(int mask, int rem) {
        if (mask == (1 << n) - 1) {
            return rem == 0 ? 1 : -1;
        }
        if (memo[mask][rem] != 0) {
            return memo[mask][rem];
        }

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) { // If nums[i] is not used
                // Handle duplicates
                if (i > 0 && nums[i] == nums[i-1] && (mask & (1 << (i - 1))) == 0) {
                    continue;
                }
                
                int newRem = (int) ((rem * p10[i] + nums[i]) % k);
                if (solve(mask | (1 << i), newRem) == 1) {
                    parent[mask][rem] = i;
                    return memo[mask][rem] = 1;
                }
            }
        }
        return memo[mask][rem] = -1;
    }
}
```
### Algorithm
- Sort the `nums` array to ensure that when we build the permutation, we can prioritize smaller numbers to find the lexicographically smallest result.
- Use a top-down dynamic programming approach with memoization. The state of our DP will be `(mask, rem)`, where `mask` is a bitmask representing the subset of `nums` used, and `rem` is the current remainder modulo `k`.
- Create a memoization table `memo[1 << N][k]` to store the results of subproblems (e.g., 1 for possible, -1 for impossible). 
- Create a `parent[1 << N][k]` table to store the index of the number chosen at each state to allow for path reconstruction.
- Define a recursive function `solve(mask, rem)` that returns whether a valid permutation can be formed from the unused numbers.
- The base case for `solve(mask, rem)` is when all numbers are used (`mask` is all 1s). It returns success if `rem == 0`, and failure otherwise.
- In the recursive step, iterate through all numbers `nums[i]`. If `nums[i]` is not in the current `mask`, recursively call `solve` for the new state `(mask | (1 << i), new_rem)`. If the recursive call is successful, it means we found a valid path. We store the chosen index `i` in `parent[mask][rem]` and return success.
- After the initial call `solve(0, 0)` completes, if a solution exists, reconstruct the permutation by backtracking through the `parent` table from the initial state.