LeetCode 216.組合せ総和III

問題リンク：216.組合せ総和III

問題説明

1から9までの数字からk個の数字を選び、その合計がnとなるすべての有効な組み合わせを見つけます。以下の条件を満たす必要があります：

• 使用できる数字は1から9まで
• 各数字は最大で1回まで使用可能
• 結果には重複する組み合わせを含めない

例1：
入力：k = 3, n = 7
出力: [[1,2,4]]
説明: 1 + 2 + 4 = 7

例2：
入力：k = 3, n = 9
出力: [[1,2,6], [1,3,5], [2,3,4]]

アプローチ

この問題はバックトラッキングアルゴリズムを使用して解決します。k個の数字を選択する必要があるため、再帰の深さはkとなります。各数字は一度しか使用できないため、再帰呼び出し時に次の数字から探索を開始します。

効率化のための枝刈り技法：

• 現在の合計が目標値nを超えた場合、その探索経路を終了
• 残りの数字個数が不足している場合、探索を早期終了

実装コード

int total = 0, solutions = 0;
int** results;
typedef struct {
    int size;
    int elements[10];
} Path;

Path currentPath = {0};

void findCombinations(int targetSum, int requiredCount, int startNum) {
    if (currentPath.size == requiredCount) {
        if (total == targetSum) {
            results[solutions] = malloc(requiredCount * sizeof(int));
            for (int i = 0; i < requiredCount; i++) {
                results[solutions][i] = currentPath.elements[i];
            }
            solutions++;
        }
        return;
    }

    for (int i = startNum; i <= 9; i++) {
        int remainingSlots = requiredCount - currentPath.size;
        if (9 - i + 1 < remainingSlots) break;
        
        if (total + i > targetSum) continue;
        
        total += i;
        currentPath.elements[currentPath.size++] = i;
        findCombinations(targetSum, requiredCount, i + 1);
        total -= i;
        currentPath.size--;
        currentPath.elements[currentPath.size] = 0;
    }
}

int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {
    results = (int**)malloc(100 * sizeof(int*));
    total = 0;
    solutions = 0;

    findCombinations(n, k, 1);

    *returnSize = solutions;
    *returnColumnSizes = (int*)malloc(sizeof(int) * solutions);
    for (int i = 0; i < solutions; i++) {
        (*returnColumnSizes)[i] = k;
    }
    return results;
}

LeetCode 17.電話番号の文字列組み合わせ

問題リンク：17.電話番号の文字列組み合わせ

問題説明

2から9までの数字のみを含む文字列が与えられた場合、それが表現可能なすべての文字の組み合わせを返します。電話のキーパッドと同じマッピングを使用します。

例1：
入力：digits = "23"
出力: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

例2：
入力：digits = ""
出力: []

アプローチ

この問題では、まず数字と文字の対応テーブルを構築します。バックトラッキングを使用して、各数字に対応する文字を順番に組み合わせていきます。

再帰関数の終了条件は、入力された数字の文字列を最後まで処理したときです。各レベルで1つの数字に対応する文字を一つ選び、次のレベルに進みます。

実装コード

char** answerList;
int answerCount = 0;
typedef struct {
    int length;
    char buffer[5];
} StringBuilder;

StringBuilder builder = {0};

const char* digitToLetters[] = {
    "",    // 0
    "",    // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz"  // 9
};

void generateCombinations(const char* inputDigits, int currentPosition) {
    if (inputDigits[currentPosition] == '\0') {
        answerList[answerCount] = malloc(builder.length + 1);
        strcpy(answerList[answerCount++], builder.buffer);
        return;
    }

    const char* letters = digitToLetters[inputDigits[currentPosition] - '0'];
    for (int i = 0; letters[i] != '\0'; i++) {
        builder.buffer[builder.length++] = letters[i];
        builder.buffer[builder.length] = '\0';
        generateCombinations(inputDigits, currentPosition + 1);
        builder.length--;
        builder.buffer[builder.length] = '\0';
    }
}

char** letterCombinations(char* digits, int* returnSize) {
    if (digits[0] == '\0') {
        *returnSize = 0;
        return NULL;
    }

    answerList = (char**)malloc(1000 * sizeof(char*));
    answerCount = 0;

    generateCombinations(digits, 0);
    *returnSize = answerCount;
    return answerList;
}