Interview Question - combine words using words

题大概是这样，一个INPUT STRING ARRAY1 比如CAT, DOG，一个INPUT STRING ARRAY 2， 比如GAT, DOC, CD, GOAT, BAD, COOL
要求第一个INPUT ARRAY的字母必须全部用，而且每个字母只能用一次，求其能组合成的INPUT STRING ARRAY2里的单词组合
比如上面这个例子，返回值会是{{GAT, DOC},{CD, GOAT}}

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=201395

My code:

private int[] charSet = new int[26];
    private int charSum = 0;
    public List<List<String>> wordSearchAnagram(List<String> input1, List<String> input2) {
        for (String s : input1) {
            for (char c : s.toCharArray()) {
                charSet[c - 'a']++;
                charSum++;
            }
        }
        List<List<String>> ret = new ArrayList<List<String>>();
        search(0, input2, new ArrayList<String>(), ret, 0);
        return ret;
    }
    
    private void search(int begin, List<String> input2, List<String> group, List<List<String>> ret, int counter) {
        if (counter > charSum) {
            return;
        }
        else if (counter == charSum) {
            int[] temp = Arrays.copyOf(charSet, 26);
            for (String s : group) {
                for (char curr : s.toCharArray()) {
                    temp[curr - 'a']--;
                    if (temp[curr - 'a'] < 0) {
                        return;
                    }
                }
            }
            ret.add(new ArrayList<String>(group));
        }
        else {
            for (int i = begin; i < input2.size(); i++) {
                group.add(input2.get(i));
                search(i + 1, input2, group, ret, counter + input2.get(i).length());
                group.remove(group.size() - 1);
            }
        }
    }

注意，如果 dictionary 里面的单词可以重复使用，那么，
search(i, ...) 而不是 search(i + 1, ...)

Anyway, Good luck, Richardo! -- 09/27/2016