Day 46: Competitive Programming Journal

Date: November 7, 2024.
Hello Everyone,

Today marks Day 46 of my competitive programming journey, and I’m here to share my progress.

What I Did Today:
I worked on two problems: Find all possible combinations of k numbers that add up to n (Backtracking) and Determine if a Sudoku board is valid (Matrix).

1. Find all possible combinations of k numbers that add up to n (Backtracking):

Problem:
Given two integers, k (number of elements) and n (target sum), find all unique combinations of k numbers between 1 and 9 that sum to n. Each number can be used only once.

Explanation:

• Use backtracking to explore all possible combinations.
• Include a number, reduce the target sum, and decrease the count k for the next recursive call.
• Backtrack when the target becomes negative or when k reaches zero.

Implementation:

void findCombinations(int k, int n, int start, vector<int>& current, vector<vector<int>>& result) {
    if (n == 0 && k == 0) { 
        result.push_back(current);
        return;
    }

    if (n < 0 || k == 0) return;

    for (int i = start; i <= 9; i++) {
        current.push_back(i);
        findCombinations(k - 1, n - i, i + 1, current, result);
        current.pop_back(); 
    }
}

vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> result;
    vector<int> current;
    findCombinations(k, n, 1, current, result);
    return result;
}

2. Determine if a Sudoku board is valid (Matrix):
Problem:
Given a partially filled 9x9 Sudoku board, determine if it is valid.

A valid board satisfies these rules:

• Each row contains unique digits from 1-9 or empty cells ('.').
• Each column contains unique digits from 1-9 or empty cells ('.').
• Each 3x3 sub-grid contains unique digits from 1-9 or empty cells ('.').

Explanation:

• Use hash sets to track the seen numbers in rows, columns, and sub-grids.
• Traverse the board and validate numbers accordingly.

Implementation:

bool isValidSudoku(vector<vector<char>>& board) {
    vector<unordered_set<char>> rows(9), cols(9), grids(9);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char num = board[i][j];
            if (num == '.') continue;

            int gridIndex = (i / 3) * 3 + (j / 3);

            if (rows[i].count(num) || cols[j].count(num) || grids[gridIndex].count(num)) {
                return false;
            }

            rows[i].insert(num);
            cols[j].insert(num);
            grids[gridIndex].insert(num);
        }
    }

    return true;
}

Reflection:
Today's problems tested my ability to implement backtracking and matrix validation efficiently. I enjoyed the logical depth involved in generating combinations and ensuring Sudoku's rules are followed systematically.

Stay tuned for more updates, and as always, happy coding!