Is there a general pattern for solving a combination?

Suppose you have two sets, such as {a, b} xy {c, d, e}, return all combinations (axyc, axyd, axye, bxyc, bxyd, bxye). I know there is a similar one, but I am not satisfied with the answer Cartesian product of arbitrary sets in Java , my question is, if there is a general approach to solving it


source to share

1 answer

Yes, there is an approach called "Backtracking", which is a common pattern for solving this problem. check here: Below is the code:

public static void main(String[] args) {
    // TODO Auto-generated method stub
List<List<Character>> lists = new ArrayList<List<Character>>();
List<Character> l1 = new ArrayList<Character>();
l1.add('a'); l1.add('b');; l1.add('c');
List<Character> l2 = new ArrayList<Character>();
List<Character> l3 = new ArrayList<Character>();
l3.add('1'); l3.add('2');
lists.add(l1); lists.add(l2); lists.add(l3);

List<String> result = new ArrayList<String>();
GenerateCombinations(lists, result, 0, new StringBuilder());


public static void GenerateCombinations(List<List<Character>> Lists, List<String> result, int    listIndex, StringBuilder combo)
    if(listIndex == Lists.size()) {
} else {
    for(int i = 0; i < Lists.get(listIndex).size(); ++i)
                //add new value 
                //get possible values in next list.
        GenerateCombinations(Lists, result, listIndex + 1, combo);
                //set back to old state.
        combo.deleteCharAt((combo.length() - 1));





All Articles