CombinationIterator - Backtracking
\nIf you like the solution plz upvote ;)\n\n\nThis a classic backtracking problem, you just need to have a clear visualization for what are you doing to solve c
```\nIf you like the solution plz upvote ;)\n```\n\nThis a classic backtracking problem, you just need to have a clear visualization for what are you doing to solve correctly. I recommend tp start with writing down the logic for combination and trace the call stack. You can refer to the example below.\n\n# The call stack will be something like \n```\nfun (characters = "abc",combinationLength=2, i = 0)\n -> fun (characters = "abc",combinationLength=2)  output = "a" left "bc"\n  -> fun (characters = "bc",combinationLength=2)  output = "ab" left "c"\n    -> fun (characters = "c",combinationLength=2)  output = "ac" left ""\n\nfun (characters = "bc",combinationLength=2 , i = 1)\n -> fun (characters = "bc",combinationLength=2)  output = "b" left "c"\n   -> fun (characters = "c",combinationLength=2)  output = "bc" left ""\n\nfun (characters = "c",combinationLength=2 , i = 2)\n -> fun (characters = "c",combinationLength=2)  output = "c" left ""\n```\nthe complexity for this piece of code of generating compination will be the <Strong>rule of compination in algebr</Strong> \nEx: \nLengthofString C combinationLength\n```\n3C2 = (3!)/((2!)-(3-2)!) = 3\n3C2 = 3  \n4C2 = 6\n```\n\nKnow we need to think about it, we need to solve to be able to know what is the return of  <Strong>hasNext()</Strong>  and  <Strong>Next()</Strong> we can do this in two ways the first one is naive. we can use list for saving all the compination in the order of computing and then do check thta will take <Strong> O(n)</Strong> for search in the list. however, we do more better through using <Strong> HashMap</Strong> that will give the answer in  <Strong> O(1)</Strong>\n\n# Code Part\n```\nclass CombinationIterator {\n    static String prev;\n    static String start;\n    static HashMap<String,String>map;\n    public CombinationIterator(String characters, int combinationLength) {\n         map = new HashMap<>();\n         start = "start";\n         prev = null;\n         buildAllCombinations("",characters,combinationLength,map);\n    }\n    \n    public String next() {\n        if(map.containsKey(start)){\n            start = map.get(start);\n        }\n        return start;\n    }\n    \n    public boolean hasNext() {\n        if(map.containsKey(start)){\n            return true;\n        }\n        return false;  \n    }\n    \n    private static void buildAllCombinations(String output,String input,int length,HashMap<String,String>map){\n       if(output.length() == length) {\n          if(prev== null || prev.equals(""))\n             map.put("start",output);\n          \n          else\n           map.put(prev,output);\n           \n           prev = output;  \n           return;\n        }\n       \n       for(int i = 0 ;i<input.length();i++){\n           \n           buildAllCombinations(output+input.charAt(i),input.substring(i+1),length, map);\n       }\n   }\n}\n```\n\n
['Backtracking', 'Combinatorics', 'Java']