Algo.Java.Dfs.Backtracking

ALL SUBSETS IS NOT ALL SUBARRAYS !!!

Lets say we have array with nums 5 1 6, what will be all combinations of these nums ? It’s a tree, so we can traverse it and get all combinations, where we add new number

Example how to get all combinations (subsets) of array with dfs

    private static void dfsBacktracking(int[] nums, int currIndex, List<Integer> prevCombination, List<List<Integer>> allCombinations) {

        List<Integer> combinationWithCurrNumber = new ArrayList<>(prevCombination);
        combinationWithCurrNumber.add(nums[currIndex]);
        allCombinations.add(combinationWithCurrNumber);

        if (currIndex == nums.length - 1) {
            return;
        }

        dfsBacktracking(nums, currIndex +1, combinationWithCurrNumber, allCombinations);
        dfsBacktracking(nums, currIndex +1, prevCombination, allCombinations);
    }

Example of iterative approach can be found here

// https://leetcode.com/problems/letter-combinations-of-a-phone-number/
class Solution {
    public List<String> letterCombinations(String digits) {

        if (digits.equals("")) {
            return new ArrayList<String>();
        } 

        HashMap<Integer, String> map = new HashMap<>();
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");

        List<String> combinations = new ArrayList<>();
        combinations.add("");

       

        for (int i = 0; i < digits.length(); i++) {
            List<String> localRes = addDigit(combinations, digits.charAt(i), map);
            combinations = localRes;
        }

        return combinations;
    }

    private List<String> addDigit(List<String> combinations, char digit, HashMap<Integer, String> lettersMap) {
        List<String> results = new ArrayList<>();
        for (int i = 0; i < combinations.size(); i++) {
            var combinations2 = addDigit(combinations.get(i), digit,lettersMap);
            results.addAll(combinations2);
        }
        return results;
    }

    private List<String> addDigit(String input, char digit, HashMap<Integer, String> lettersMap) {
        List<String> res = new ArrayList<>();
        String letters = lettersMap.get(Character.digit(digit, 10));
        for (int i = 0; i < letters.length(); i++) {
            res.add(input + letters.charAt(i));
        }

        return res;
    };
}