search – Page 11 – Huahua’s Tech Road

题目大意：输出所有用k个数的和为n的组合。可以使用的元素是1到9。

Problem:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

1	[[1,2,6], [1,3,5], [2,3,4]]

Idea:

DFS + backtracking

bit

Solution:

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

vector<int> cur;

dfs(k, n, 1, cur, ans);

return ans;

}

private:

// Use k numbers (>= s) to sum up to n

void dfs(int k, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (k == 0) {

if (n == 0) ans.push_back(cur);

return;

}

for (int i = s; i <= 9; ++i) {

if (i > n) return;

cur.push_back(i);

dfs(k - 1, n - i, i + 1, cur, ans);

cur.pop_back();

}

};

C++ / binary

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

// 2^9, generate all combinations of [1 .. 9]

for (int i = 0; i < (1 << 9); ++i) {

vector<int> cur;

int sum = 0;

// Use j if (j - 1)-th bit is 1

for (int j = 1; j <= 9; ++j)

if (i & (1 << (j - 1))) {

sum += j;

cur.push_back(j);

}

if (sum == n && cur.size() == k)

ans.push_back(cur);

}

return ans;

}

};

Python

class Solution:

def combinationSum3(self, k, n):

def dfs(k, n, s, cur, ans):

if k == 0 and n == 0:

ans.append(list(cur))

for i in range(s, min(n + 1, 10)):

dfs(k - 1, n - i, i + 1, cur + [i], ans)

ans = []

dfs(k, n, 1, [], ans)

return ans

Related problems:

C++

class Solution {

public:

bool exist(vector<vector<char>> &board, string word) {

if(board.size()==0) return false;

h = board.size();

w = board[0].size();

for(int i=0;i<w;i++)

for(int j=0;j<h;j++)

if(search(board, word, 0, i, j)) return true;

return false;

}

bool search(vector<vector<char>> &board,

const string& word, int d, int x, int y) {

if(x<0 || x==w || y<0 || y==h || word[d] != board[y][x])

return false;

// Found the last char of the word

if(d==word.length()-1)

return true;

char cur = board[y][x];

board[y][x] = 0;

bool found = search(board, word, d+1, x+1, y)

|| search(board, word, d+1, x-1, y)

|| search(board, word, d+1, x, y+1)

|| search(board, word, d+1, x, y-1);

board[y][x] = cur;

return found;

}

private:

int w;

int h;

};

Python

# Author: Huahua, running time: 216 ms

class Solution:

def exist(self, board: List[List[str]], word: str) -> bool:

if not board: return False

h, w = len(board), len(board[0])

def search(d: int, x: int, y: int) -> bool:

if x < 0 or x == w or y < 0 or y == h or word[d] != board[y][x]:

return False

if d == len(word) - 1: return True

cur = board[y][x]

board[y][x] = ''

found = search(d + 1, x + 1, y) or search(d + 1, x - 1, y) or search(d + 1, x, y + 1) or search(d + 1, x, y - 1)

board[y][x] = cur

return found

return any(search(0, j, i) for i in range(h) for j in range(w))

Posts tagged as “search”

花花酱 LeetCode 216. Combination Sum III

花花酱 LeetCode 79. Word Search

C++

Python