Javaで配列から異なる要素の組み合わせを見つける方法

再帰を使用したビットマスク法: この方法では、ビットマスクを使って要素の組み合わせを生成します。配列の各要素に対して、要素を選択するかしないかの2つの選択肢があります。これをビットマスクとして表現し、すべての可能な組み合わせを生成します。

public class CombinationFinder {
    public static void findCombinations(int[] arr) {
        int n = arr.length;
        int totalCombinations = 1 << n;
        for (int i = 1; i < totalCombinations; i++) {
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) {
                    System.out.print(arr[j] + " ");
                }
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        findCombinations(arr);
    }
}

出力:

再帰を使用したバックトラッキング法: この方法では、再帰を使って可能な組み合わせを生成します。配列の各要素に対して、要素を選択するかしないかの2つの選択肢を再帰的に探索し、組み合わせを生成します。

public class CombinationFinder {
    public static void findCombinations(int[] arr) {
        findCombinationsHelper(arr, new ArrayList<>(), 0);
    }
    private static void findCombinationsHelper(int[] arr, List<Integer> currentCombination, int index) {
        if (index == arr.length) {
            System.out.println(currentCombination);
            return;
        }
// 要素を選択しない場合
        findCombinationsHelper(arr, currentCombination, index + 1);
        // 要素を選択する場合
        currentCombination.add(arr[index]);
        findCombinationsHelper(arr, currentCombination, index + 1);
        currentCombination.remove(currentCombination.size() - 1);
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        findCombinations(arr);
    }
}

出力:

[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

これらの方法を使用して、異なる要素の組み合わせを見つけることができます。どちらの方法も再帰を使用していますが、アプローチが異なるため、出力の順序が異なることに注意してください。また、配列の要素数が多い場合は、組み合わせの数が爆発的に増えるため、計算量に注意してください。