花花酱 LeetCode 40. Combination Sum II

By zxi on October 15, 2017

Problem:

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.
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]

]

Idea:

DFS

Solution:

C++ / set

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

set<vector<int>> ans;

std::sort(candidates.begin(), candidates.end());

vector<int> curr;

dfs(candidates, target, 0, ans, curr);

return vector<vector<int>>(ans.begin(), ans.end());

}

private:

void dfs(const vector<int>& candidates,

int target, int s,

set<vector<int>>& ans,

vector<int>& curr) {

if (target == 0) {

ans.insert(curr);

return;

}

for (int i = s; i < candidates.size(); ++i) {

int num = candidates[i];

if (num > target) return;

curr.push_back(num);

dfs(candidates, target - num, i + 1, ans, curr);

curr.pop_back();

}

};

C++ / vector

// Author: Huahua

// Runtime: 9ms

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

vector<vector<int>> ans;

std::sort(candidates.begin(), candidates.end());

vector<int> curr;

dfs(candidates, target, 0, ans, curr);

return ans;

}

private:

void dfs(const vector<int>& candidates,

int target, int s,

vector<vector<int>>& ans,

vector<int>& curr) {

if (target == 0) {

ans.push_back(curr);

return;

}

for (int i = s; i < candidates.size(); ++i) {

int num = candidates[i];

if (num > target) return;

if (i > s && candidates[i] == candidates[i - 1]) continue;

curr.push_back(num);

dfs(candidates, target - num, i + 1, ans, curr);

curr.pop_back();

}

};

花花酱 LeetCode 39. Combination Sum

By zxi on October 3, 2017

Problem:

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[

[7],

[2, 2, 3]

]

Idea:

DFS

Solution: C++

class Solution {

public:

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

vector<vector<int>> ans;

vector<int> cur;

std::sort(candidates.begin(), candidates.end());

dfs(candidates, target, 0, cur, ans);

return ans;

}

private:

void dfs(vector<int>& candidates, int target, int s, vector<int>& cur, vector<vector<int>>& ans) {

if (target == 0) {

ans.push_back(cur);

return;

}

for (int i = s; i < candidates.size(); ++i) {

if (candidates[i] > target) break;

cur.push_back(candidates[i]);

dfs(candidates, target - candidates[i], i, cur, ans);

cur.pop_back();

}

};

Python

"""

Author: Huahua

Runtime: 75 ms (batter than 97.04%)

"""

class Solution(object):

def combinationSum(self, candidates, target):

def dfs(candidates, target, s, curr, ans):

if target == 0:

ans.append(curr[:])

return

for i in xrange(s, len(candidates)):

if candidates[i] > target: return

curr.append(candidates[i])

dfs(candidates, target - candidates[i], i, curr, ans)

curr.pop()

ans = []

candidates.sort()

dfs(candidates, target, 0, [], ans);

return ans

花花酱 Leetcode 140. Word Break II

By zxi on September 2, 2017

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution

Time complexity: O(2^n)

Space complexity: O(2^n)

C++

// Author: Huahua

class Solution {

public:

vector<string> wordBreak(string s, vector<string>& wordDict) {

unordered_set<string> dict(wordDict.cbegin(), wordDict.cend());

return wordBreak(s, dict);

}

private:

// >> append({"cats and", "cat sand"}, "dog");

// {"cats and dog", "cat sand dog"}

vector<string> append(const vector<string>& prefixes, const string& word) {

vector<string> results;

for(const auto& prefix : prefixes)

results.push_back(prefix + " " + word);

return results;

}

const vector<string>& wordBreak(string s, unordered_set<string>& dict) {

// Already in memory, return directly

if(mem_.count(s)) return mem_[s];

// Answer for s

vector<string> ans;

// s in dict, add it to the answer array

if(dict.count(s))

ans.push_back(s);

for(int j=1;j<s.length();++j) {

// Check whether right part is a word

const string& right = s.substr(j);

if (!dict.count(right)) continue;

// Get the ans for left part

const string& left = s.substr(0, j);

const vector<string> left_ans =

append(wordBreak(left, dict), right);

// Notice, can not use mem_ here,

// since we haven't got the ans for s yet.

ans.insert(ans.end(), left_ans.begin(), left_ans.end());

}

// memorize and return

mem_[s].swap(ans);

return mem_[s];

}

private:

unordered_map<string, vector<string>> mem_;

};

Python3

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def wordBreak(self, s, wordDict):

words = set(wordDict)

mem = {}

def wordBreak(s):

if s in mem: return mem[s]

ans = []

if s in words: ans.append(s)

for i in range(1, len(s)):

right = s[i:]

if right not in words: continue

ans += [w + " " + right for w in wordBreak(s[0:i])]

mem[s] = ans

return mem[s]

return wordBreak(s)

Posts tagged as “combination”

花花酱 LeetCode 40. Combination Sum II

花花酱 LeetCode 39. Combination Sum

花花酱 Leetcode 140. Word Break II

Problem

Solution

Related Problems