Menu Combination Sum - Airbnb

https://github.com/allaboutjst/airbnb/blob/master/README.md
Given a menu (list of items prices), find all possible combinations of items that sum a particular value K. (A variation of the typical 2sum/Nsum questions).

        private void search(List<List<Double>> res, int[] centsPrices, int start, int centsTarget,
                            List<Double> curCombo, double[] prices) {
            if (centsTarget == 0) {
                res.add(new ArrayList<>(curCombo));
                return;
            }

            for (int i = start; i < centsPrices.length; i++) {
                if (i > start && centsPrices[i] == centsPrices[i - 1]) {
                    continue;
                }
                if (centsPrices[i] > centsTarget) {
                    break;
                }
                curCombo.add(prices[i]);
                search(res, centsPrices, i + 1, centsTarget - centsPrices[i], curCombo, prices);
                curCombo.remove(curCombo.size() - 1);
            }
        }

        public List<List<Double>> getCombos(double[] prices, double target) {
            List<List<Double>> res = new ArrayList<>();
            if (prices == null || prices.length == 0 || target <= 0) {
                return res;
            }

            int centsTarget = (int) Math.round(target * 100);
            Arrays.sort(prices);
            int[] centsPrices = new int[prices.length];
            for (int i = 0; i < prices.length; i++) {
                centsPrices[i] = (int) Math.round(prices[i] * 100);
            }

            search(res, centsPrices, 0, centsTarget, new ArrayList<>(), prices);
            return res;
        }

Permuting Lists of Lists - Print all possible words from phone digits

Permuting Lists of Lists - Print all possible words from phone digits - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given a list of arraylists containing elements, write a function that prints out the permutations of of the elements such that, each of the permutation set contains only 1 element from each arraylist and there are no duplicates in the list of permutation sets.

For example: consider the following lists

L1= {a1,b1,c1,d1} 
L2= {a2,b2,c2} 
L3= {a3, b3, c3} 

Valid Permutations are: 
{a1, a2, a3}
{a1, a2, b3}
{a1, a2, c3}
{a1, b2, a3}
{a1, b2, b3}
{a1, b2, c3}
... 
... 
...
{d1, c2, a3}
{d1, c2, b3}
{d1, c2, c3}

Please note that 
{a1,b2,c3} is same set as {b2,a1,c3}

We can solve this problem similar to we did solve the combination problem in a previous post here. This problem can be solved similarly where we consider the the input list as a multidimensional string that contains a list of string at each position. Anytime we will consider one single item. So, for each string in first list we do recurse to all other lists to find the combinations. We print the result whenever we reach the last list and output contains one elements from each of the n lists. 

public static void permuteList(String[][] list, int start, ArrayList<String> perms // use linkedlist){
 if(start == list.length){
  if(perms.size() == list.length)
   System.out.println(perms.toString());
  return;
 }
 
 for(int i = 0; i < list[start].length; i++){
  perms.add(list[start][i]);
  for(int j = start+1; j <= list.length; j++){
   permuteList(list, j, perms);
  }// change to perms.removeLast();
  perms.remove(list[start][i]); // change to remove perms.remove(perms.size() - 1);
 }
}

Read full article from Permuting Lists of Lists - Print all possible words from phone digits - Algorithms and Problem SolvingAlgorithms and Problem Solving

VMware Coding Challenge: Possible Scores

VMware Coding Challenge: Possible Scores

Combination Sum I 那道题的变体

 5     static int is_score_possible(int score, int[] increments) {
 6         Arrays.sort(increments);
 7         ArrayList<Integer> res = new ArrayList<Integer>();
 8         res.add(0);
 9         helper(res, increments, score, 0);
10         return res.get(0);
11     }
12 
13     public static void helper(ArrayList<Integer> res, int[] increments, int score, int start) {
14         if (score < 0) return;
15         if (score == 0) {
16             res.set(0, 1);
17             return;
18         }
19         for (int i=start; i<increments.length; i++) {
20             if (i>start && increments[i] == increments[i-1]) continue;
21             helper(res, increments, score-increments[i], i);
22             if (res.get(0) == 1) return;
23         }
24     }

Combination Misc

Generate all combination which prints star in place of absent characters
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/CombinationWithStar.java
    public void combine(char input[], int pos, boolean used[]){
        printArray(input, used);
        for(int i= pos; i < input.length; i++){
            used[i] = true;
            combine(input, i+1, used);
            used[i] = false;
        }
    }
 
    private void printArray(char result[], boolean used[]){
        for(int i=0; i < used.length; i++){
            if(used[i]){
                System.out.print(result[i] + " ");
            }else{
                System.out.print("* ");
            }
        }
        System.out.println();
    }
Combination with repetition of characters allowed
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/CombinationWithReptition.java
    public void combination(char input[],int count[]){
        int len =0;
        for(int i=0; i < count.length; i++){
            len += count[i];
        }
        char result[] = new char[len];
        combination(input,count,0,0,result,0);
    }
 
    private void combination(char input[],int count[],int pos, int countPos, char result[],int len){
     
        if(pos == input.length){
            return;
        }
        print(result,len);
        for(int i=pos; i < input.length; i++){
            if(countPos < count[i]){
                result[len] = input[i];
                combination(input,count,i,countPos+1,result,len+1);
            }
            countPos = 0;
        }
    }
 
    public void combination(char input[]){
        Arrays.sort(input);
        char result[] = new char[input.length];
        combination(input,0,result,0);
    }
 
    private void combination(char input[],int pos,char result[],int len){
        print(result,len);
        for(int i=pos; i < input.length;)
        {
            //idea is to find first non repeated char position j.
            // then keep adding one element from repetition and find combination for
            //rest of the array
            //e.g aaabbc i = 0 j = 3 we do a{bbc} then aa{bbc} aaa{bbc}
            int j= i;
            while(j < input.length && input[i] == input[j]){
                j++;
            }
            int tempLen = len;
            for(int k=i; k < j; k++){
                result[len] = input[i];
                combination(input,j,result,len+1);
                len++;
            }
            len = tempLen;
            i = j;
        }
    }
 
    private void print(char result[],int pos){
        for(int i=0; i < pos; i++){
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/PrintPermInSortedOrder.java
    public void printPerm(char arr[], int current, boolean used[],char []result){
     
        if(current == arr.length){
            printArray(result);
        }
        for(int i=0; i < arr.length; i++){
            if(!used[i]){
                used[i] = true;
                result[current] = arr[i];
                printPerm(arr, current+1, used,result);
                used[i] = false;
            }
        }
     
    }
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/StringPermutationRotation.java
    public void permute(char[] str,int pos){
        if(pos == str.length){
            printArray(str);
            return;
        }
        for(int i=pos; i < str.length; i++){
            swap(str,pos,i);
            permute(str,pos+1);
            swap(str,pos,i);
        }
    }
Given an input and total, print all combinations with repetitions in this input which sums to given total.
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/PrintSumCombination.java
  private void print(int input[], int sum, List<Integer >result) {  
      if(sum < 0) {
          return;
      }
      if(sum == 0) {
          result.stream().forEach(i -> System.out.print(i + " "));
          System.out.println();
          return;
      }
   
   
      for(int i=0; i < input.length; i++) {
          result.add(input[i]);
          print(input, sum - input[i], result);
          result.remove(result.size()-1);
      }
  }
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/WordCombination.java
 * Given a list of list of Strings. Print cartesian product of lists.
 * input -> {"Hello", "World"} , {"Game"}, {"Go","Home"}
 * output ->
 * Hello Game Go
 * Hellow Game Home
 * World Game Go
 * World Game Home
    public void printCombinations(List<List<String>> input) {
        int[] result = new int[input.size()];
        print(input,result, 0);
    }

    private void print(List<List<String>> input, int[] result, int pos) {

        if(pos == result.length){
            for (int i = 0; i < input.size(); i++) {
                System.out.print(input.get(i).get(result[i]) + " ");
            }
            System.out.println();
            return;
        }

        for(int i=0; i < input.get(pos).size(); i++){
            result[pos] = i;
            print(input,result, pos+1);

        }
    }
Given two strings, generate all interleavings of these strings
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/StringInterleaving.java
    public void interleaving(char[] str1,char[] str2,int len1,int len2,int current, char []result){
       
        if(current == result.length){
            printArray(result);
            return;
        }

        if(len1 < str1.length){
            result[current] = str1[len1];
            interleaving(str1, str2, len1+1, len2, current+1, result);
        }
        if(len2 < str2.length){
            result[current] = str2[len2];
            interleaving(str1,str2,len1,len2+1,current+1,result);
        }
    }
        char[] result = new char[str1.length() + str2.length()];
        si.interleaving(str1.toCharArray(), str2.toCharArray(), 0, 0, 0, result);  
Generate all possible string combinations of a given phone number
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/KeyPadPermutation.java
    private void permute(int input[], int pos, char result[]) {
        if (pos == input.length) {
            for (int i = 0; i < result.length; i++) {
                System.out.print(result[i]);
            }
            System.out.println();
            return;
        }

        char[] str = getCharSetForNumber(input[pos]);
        for (char ch : str) {
            result[pos] = ch;
            permute(input, pos+1, result);
        }
    }

    private char[] getCharSetForNumber(int num) {
        switch(num){
            case 1 : return "abc".toCharArray();
            case 2 : return "def".toCharArray();
            case 3: return "ghi".toCharArray();
            case 4: return "jkl".toCharArray();
            case 5: return "mno".toCharArray();
            case 6: return "pqrs".toCharArray();
            case 8: return "tuv".toCharArray();
            case 9: return "wxyz".toCharArray();
        }
        throw new IllegalArgumentException();
    }

Buttercola: Zenefits: Combinations

Buttercola: Zenefits: Combinations
找出一个string里面长度为n （n小于等于string的长度）的所有组合。
这个比较简单 考虑了一下dupilcate 字母

    public List<String> combination(String s, int k) {

        List<String> result = new ArrayList<>();

        if (s == null || s.length() == 0 || k <= 0) {

            return result;

        }

         

        StringBuffer sb = new StringBuffer();

        combinationHelper(0, s, 0, k, sb, result);

         

        return result;

    }

     

    private void combinationHelper(int start, String s, int num,

                                   int k, StringBuffer sb, List<String> result) {

        if (num == k) {

            result.add(sb.toString());

            return;

        }

         

        for (int i = start; i < s.length(); i++) {

            sb.append(s.charAt(i));

            combinationHelper(i + 1, s, num + 1, k, sb, result);

            sb.deleteCharAt(sb.length() - 1);

        }

    }

     

    public static void main(String[] args) {

        Solution solution = new Solution();

        String s = "abcd";

        List<String> result = solution.combination(s, 2);

         

        for (String i : result) {

            System.out.println(i);

        }

    }

Read full article from Buttercola: Zenefits: Combinations