Program to find all possible smart arrays that can be constructed using a string of digits. A smart array is an array where if we remove spaces among integers, it becomes the same string from which it has been created. Also, a smart array should not have any leading zeroes.

Example 1. Input string = “1317”

output=[1, 3, 1, 7],[1, 3, 17],[1, 31, 7],[1, 317],[13, 1, 7],[13, 17],

[131, 7],[1317]

Total possible arrays: 8

Example 2. Input string = “1000”

output = [1000]

Total possible arrays: 1

Approach : Backtracking with Depth First Search, not sure if I can use DP memoization for finding all possible combination of arrays.

import java.util.ArrayList;
import java.util.List;

public class MainProgram {

public static void main(String[] args) {
String intString = "1317";
System.out.println("Total possible arrays:
"+findSmartArrays(intString,0,new ArrayList<>()));

}

public static int findSmartArrays(String intString, int i,
List<Integer> list){
if(i==intString.length()) {
System.out.println(list); return 1;
}
if(intString.charAt(i)=='0') return 0;

int num=0; int count=0;

for(int j=i;j<intString.length();j++){

num=num*10+intString.charAt(j)-'0';
list.add(num);
count+=findSmartArrays(intString,j+1,list);
list.remove(list.size()-1);

}

return count;

}
}
/*
Call stack for better understanding
dfs("1317",2000,0,{}) - > loop(j=0<4) - > dfs("1317",2000,1,{1}) - > loop(j=1<4) - > dfs("1317",2000,2,{1,3})
- > loop(j=2<4) - > dfs("1317",2000,3,{1,3,1}) - > loop(j=3<4)
- > dfs("1317",2000,4,{1,3,1,7}) - >
4=="1317".length() print list {1,3,1,7}, return 1->to maintain
total count
Remove last element from list to generate different combination
go back to loop(j=3<4)->loop(j=4<4) break and return to stack
holding call to dfs("1317",2000,3,{1,3,1})
Remove last element from list to generate different combination
go back to loop(j=2<4)->loop(j=3<4) - >
dfs("1317",2000,4,{1,3,17}) - >
4=="1317".length() print list {1,3,17}, return 1->to maintain
total count
Remove last element from list to generate different combination
go back to loop(j=3<4)->loop(j=4<4) break and return to stack
holding call to dfs("1317",2000,2,{1,3}) and so on....!!
*/

Program’s output

[1, 3, 1, 7]
[1, 3, 17]
[1, 31, 7]
[1, 317]
[13, 1, 7]
[13, 17]
[131, 7]
[1317]
Total possible arrays: 8

Time complexity : O(2^(n-1–c)) where n is length of input string and c is no. of 0s in string.

Space complexity : O(n), where n is maximum size of list to store smart array.

Please write comments if you find anything incorrect, or you want to share more optimized solution about the topic discussed above. I would really appreciate your efforts..!!

Software Developer