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