Day 57 #37, #40, Sudoku Solver, Combination Sum II

Search in Rotated Sorted Array
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

------------------------------------------
set up three 2D arrays as caches to store used numbers in each row, column and sub-block

class Solution {
public:
    bool sudoku (vector<vector<char> > &board, vector<vector<bool> > &rows, 
            vector<vector<bool> > &cols, vector<vector<bool> > &subs, int index) {
        if (index == 81) {
            return true;
        }
        int rowIndex = index / 9;
        int colIndex = index % 9;
        
        if (board[rowIndex][colIndex] == '.') {
            for (int i = 0; i < 9; i++) {
                if (!(rows[rowIndex][i] || cols[colIndex][i] || subs[(rowIndex / 3) * 3 + colIndex / 3][i])) {
                    board[rowIndex][colIndex] = '1' + i;
                    rows[rowIndex][i] = true;
                    cols[colIndex][i] = true;
                    subs[rowIndex / 3 * 3 + colIndex / 3][i] = true;
                    
                    // if conditions is false, backtrack
                    if (!sudoku(board, rows, cols, subs,index + 1)) {
                        board[rowIndex][colIndex] = '.';
                        rows[rowIndex][i] = false;
                        cols[colIndex][i] = false;
                        subs[rowIndex / 3 * 3 + colIndex / 3][i] = false;
                    }else {
                        return true;
                    }
                }
            }
            return false;
        }else {
            // if slot is filled already
            return sudoku(board, rows, cols, subs,index + 1);
        }
    }

    void solveSudoku(vector<vector<char> > &board) {
        // declare and populate caches
        vector<vector<bool> > rows(9,vector<bool>(9,false));
        vector<vector<bool> > cols(9,vector<bool>(9,false));
        vector<vector<bool> > subs(9,vector<bool>(9,false));
        for (int rowIndex = 0; rowIndex < 9; rowIndex++) {
            for (int colIndex = 0; colIndex < 9; colIndex++) {
                if (board[rowIndex][colIndex] != '.') {
                    int val = board[rowIndex][colIndex] - '1';
                    rows[rowIndex][val] = true;
                    cols[colIndex][val] = true;
                    subs[(rowIndex / 3) * 3 + colIndex / 3][val] = true;
                }
            }
        }
        
        // recursive call starts here
        sudoku(board,rows,cols,subs,0);
    }
};

Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
------------------------------------------------------------
Similar to #39 Combination Sum

class Solution {
public:
    void comb (vector<int>& candidates, int target, vector<vector<int> > &ret, vector<int> cur,int start) {
        if (target == 0) {
            ret.push_back(cur);
        }else {
            for (int i = start; i < candidates.size(); i++) {
                if (target - candidates[i] >= 0) {
                    vector<int> v= cur;
                    v.push_back(candidates[i]);
                    comb(candidates,target-candidates[i],ret,v,i+1); // no element can be re-used, so i + 1
                }
                
                // skip duplicates 
                while (candidates.size() - 1 > i && candidates[i] == candidates[i + 1]) {
                    i++;
                }
            }
        }
    }

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        vector<vector<int> > ret;
        vector<int> cur;
        comb(num,target,ret,cur,0);
        return ret;
    }
};

类似

class Solution {
public:
    void helper(vector<vector<int>> &rt,vector<int>& candidates, vector<int> cur,int target,int index) {
        if (target == 0) {
            rt.push_back(cur);
            return;
        }
        
         if (target < 0 || index >= candidates.size()) return;
        
        vector<int> temp = cur;
        temp.push_back(candidates[index]);
        helper(rt,candidates,temp,target - candidates[index],index + 1);

        while (index + 1 < candidates.size() && candidates[index] == candidates[index + 1]) {
            index++;
        }
        helper(rt,candidates,cur,target,index + 1);
        
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int>> rt;
        vector<int> cur;
        helper(rt,candidates,cur,target,0);
        
        return rt;
    }
};