Concatenated Divisibility

• 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.

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.

1class Solution {2    int[] nums;3    int n;4    int k;5    long[] p10;6    int[][] memo; // 0: not computed, 1: possible, -1: impossible7    int[][] parent; // stores the index of the number chosen8 9    public int[] concatenatedDivisibility(int[] nums, int k) {10        this.n = nums.length;11        this.nums = nums;12        this.k = k;13        14        Arrays.sort(this.nums);15 16        this.p10 = new long[n];17        for (int i = 0; i < n; i++) {18            p10[i] = (long) Math.pow(10, String.valueOf(nums[i]).length());19        }20 21        this.memo = new int[1 << n][k];22        this.parent = new int[1 << n][k];23 24        if (solve(0, 0) == -1) {25            return new int[0];26        }27 28        // Reconstruct path29        int[] result = new int[n];30        int currentMask = 0;31        int currentRem = 0;32        for (int i = 0; i < n; i++) {33            int index = parent[currentMask][currentRem];34            result[i] = this.nums[index];35            currentRem = (int) ((currentRem * p10[index] + this.nums[index]) % k);36            currentMask |= (1 << index);37        }38        return result;39    }40 41    private int solve(int mask, int rem) {42        if (mask == (1 << n) - 1) {43            return rem == 0 ? 1 : -1;44        }45        if (memo[mask][rem] != 0) {46            return memo[mask][rem];47        }48 49        for (int i = 0; i < n; i++) {50            if ((mask & (1 << i)) == 0) { // If nums[i] is not used51                // Handle duplicates52                if (i > 0 && nums[i] == nums[i-1] && (mask & (1 << (i - 1))) == 0) {53                    continue;54                }55                56                int newRem = (int) ((rem * p10[i] + nums[i]) % k);57                if (solve(mask | (1 << i), newRem) == 1) {58                    parent[mask][rem] = i;59                    return memo[mask][rem] = 1;60                }61            }62        }63        return memo[mask][rem] = -1;64    }65}