Question

216. Combination Sum III

中文文档

Description

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return _a list of all possible valid combinations_. The list must not contain the same combination twice, and the combinations may be returned in any order.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

 

Constraints:

• 2 <= k <= 9
• 1 <= n <= 60

Solutions

Solution 1

class Solution:
  def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    def dfs(i: int, s: int):
      if s == 0:
        if len(t) == k:
          ans.append(t[:])
        return
      if i > 9 or i > s or len(t) >= k:
        return
      t.append(i)
      dfs(i + 1, s - i)
      t.pop()
      dfs(i + 1, s)

    ans = []
    t = []
    dfs(1, n)
    return ans

class Solution {
  private List<List<Integer>> ans = new ArrayList<>();
  private List<Integer> t = new ArrayList<>();
  private int k;

  public List<List<Integer>> combinationSum3(int k, int n) {
    this.k = k;
    dfs(1, n);
    return ans;
  }

  private void dfs(int i, int s) {
    if (s == 0) {
      if (t.size() == k) {
        ans.add(new ArrayList<>(t));
      }
      return;
    }
    if (i > 9 || i > s || t.size() >= k) {
      return;
    }
    t.add(i);
    dfs(i + 1, s - i);
    t.remove(t.size() - 1);
    dfs(i + 1, s);
  }
}

class Solution {
public:
  vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> ans;
    vector<int> t;
    function<void(int, int)> dfs = [&](int i, int s) {
      if (s == 0) {
        if (t.size() == k) {
          ans.emplace_back(t);
        }
        return;
      }
      if (i > 9 || i > s || t.size() >= k) {
        return;
      }
      t.emplace_back(i);
      dfs(i + 1, s - i);
      t.pop_back();
      dfs(i + 1, s);
    };
    dfs(1, n);
    return ans;
  }
};

func combinationSum3(k int, n int) (ans [][]int) {
  t := []int{}
  var dfs func(i, s int)
  dfs = func(i, s int) {
    if s == 0 {
      if len(t) == k {
        ans = append(ans, slices.Clone(t))
      }
      return
    }
    if i > 9 || i > s || len(t) >= k {
      return
    }
    t = append(t, i)
    dfs(i+1, s-i)
    t = t[:len(t)-1]
    dfs(i+1, s)
  }
  dfs(1, n)
  return
}

function combinationSum3(k: number, n: number): number[][] {
  const ans: number[][] = [];
  const t: number[] = [];
  const dfs = (i: number, s: number) => {
    if (s === 0) {
      if (t.length === k) {
        ans.push(t.slice());
      }
      return;
    }
    if (i > 9 || i > s || t.length >= k) {
      return;
    }
    t.push(i);
    dfs(i + 1, s - i);
    t.pop();
    dfs(i + 1, s);
  };
  dfs(1, n);
  return ans;
}

impl Solution {
  #[allow(dead_code)]
  pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
    let mut ret = Vec::new();
    let mut candidates = (1..=9).collect();
    let mut cur_vec = Vec::new();
    Self::dfs(n, k, 0, 0, &mut cur_vec, &mut candidates, &mut ret);
    ret
  }

  #[allow(dead_code)]
  fn dfs(
    target: i32,
    length: i32,
    cur_index: usize,
    cur_sum: i32,
    cur_vec: &mut Vec<i32>,
    candidates: &Vec<i32>,
    ans: &mut Vec<Vec<i32>>
  ) {
    if cur_sum > target || cur_vec.len() > (length as usize) {
      // No answer for this
      return;
    }
    if cur_sum == target && cur_vec.len() == (length as usize) {
      // We get an answer
      ans.push(cur_vec.clone());
      return;
    }
    for i in cur_index..candidates.len() {
      cur_vec.push(candidates[i]);
      Self::dfs(target, length, i + 1, cur_sum + candidates[i], cur_vec, candidates, ans);
      cur_vec.pop().unwrap();
    }
  }
}

public class Solution {
  private List<IList<int>> ans = new List<IList<int>>();
  private List<int> t = new List<int>();
  private int k;

  public IList<IList<int>> CombinationSum3(int k, int n) {
    this.k = k;
    dfs(1, n);
    return ans;
  }

  private void dfs(int i, int s) {
    if (s == 0) {
      if (t.Count == k) {
        ans.Add(new List<int>(t));
      }
      return;
    }
    if (i > 9 || i > s || t.Count >= k) {
      return;
    }
    t.Add(i);
    dfs(i + 1, s - i);
    t.RemoveAt(t.Count - 1);
    dfs(i + 1, s);
  }
}

Solution 2

class Solution:
  def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    def dfs(i: int, s: int):
      if s == 0:
        if len(t) == k:
          ans.append(t[:])
        return
      if i > 9 or i > s or len(t) >= k:
        return
      for j in range(i, 10):
        t.append(j)
        dfs(j + 1, s - j)
        t.pop()

    ans = []
    t = []
    dfs(1, n)
    return ans

class Solution {
  private List<List<Integer>> ans = new ArrayList<>();
  private List<Integer> t = new ArrayList<>();
  private int k;

  public List<List<Integer>> combinationSum3(int k, int n) {
    this.k = k;
    dfs(1, n);
    return ans;
  }

  private void dfs(int i, int s) {
    if (s == 0) {
      if (t.size() == k) {
        ans.add(new ArrayList<>(t));
      }
      return;
    }
    if (i > 9 || i > s || t.size() >= k) {
      return;
    }
    for (int j = i; j <= 9; ++j) {
      t.add(j);
      dfs(j + 1, s - j);
      t.remove(t.size() - 1);
    }
  }
}

class Solution {
public:
  vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> ans;
    vector<int> t;
    function<void(int, int)> dfs = [&](int i, int s) {
      if (s == 0) {
        if (t.size() == k) {
          ans.emplace_back(t);
        }
        return;
      }
      if (i > 9 || i > s || t.size() >= k) {
        return;
      }
      for (int j = i; j <= 9; ++j) {
        t.emplace_back(j);
        dfs(j + 1, s - j);
        t.pop_back();
      }
    };
    dfs(1, n);
    return ans;
  }
};

func combinationSum3(k int, n int) (ans [][]int) {
  t := []int{}
  var dfs func(i, s int)
  dfs = func(i, s int) {
    if s == 0 {
      if len(t) == k {
        ans = append(ans, slices.Clone(t))
      }
      return
    }
    if i > 9 || i > s || len(t) >= k {
      return
    }
    for j := i; j <= 9; j++ {
      t = append(t, j)
      dfs(j+1, s-j)
      t = t[:len(t)-1]
    }
  }
  dfs(1, n)
  return
}

function combinationSum3(k: number, n: number): number[][] {
  const ans: number[][] = [];
  const t: number[] = [];
  const dfs = (i: number, s: number) => {
    if (s === 0) {
      if (t.length === k) {
        ans.push(t.slice());
      }
      return;
    }
    if (i > 9 || i > s || t.length >= k) {
      return;
    }
    for (let j = i; j <= 9; ++j) {
      t.push(j);
      dfs(j + 1, s - j);
      t.pop();
    }
  };
  dfs(1, n);
  return ans;
}

public class Solution {
  private List<IList<int>> ans = new List<IList<int>>();
  private List<int> t = new List<int>();
  private int k;

  public IList<IList<int>> CombinationSum3(int k, int n) {
    this.k = k;
    dfs(1, n);
    return ans;
  }

  private void dfs(int i, int s) {
    if (s == 0) {
      if (t.Count == k) {
        ans.Add(new List<int>(t));
      }
      return;
    }
    if (i > 9 || i > s || t.Count >= k) {
      return;
    }
    for (int j = i; j <= 9; ++j) {
      t.Add(j);
      dfs(j + 1, s - j);
      t.RemoveAt(t.Count - 1);
    }
  }
}

Solution 3

class Solution:
  def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    ans = []
    for mask in range(1 << 9):
      if mask.bit_count() == k:
        t = [i + 1 for i in range(9) if mask >> i & 1]
        if sum(t) == n:
          ans.append(t)
    return ans

class Solution {
  public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> ans = new ArrayList<>();
    for (int mask = 0; mask < 1 << 9; ++mask) {
      if (Integer.bitCount(mask) == k) {
        List<Integer> t = new ArrayList<>();
        int s = 0;
        for (int i = 0; i < 9; ++i) {
          if ((mask >> i & 1) == 1) {
            s += (i + 1);
            t.add(i + 1);
          }
        }
        if (s == n) {
          ans.add(t);
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> ans;
    for (int mask = 0; mask < 1 << 9; ++mask) {
      if (__builtin_popcount(mask) == k) {
        int s = 0;
        vector<int> t;
        for (int i = 0; i < 9; ++i) {
          if (mask >> i & 1) {
            t.push_back(i + 1);
            s += i + 1;
          }
        }
        if (s == n) {
          ans.emplace_back(t);
        }
      }
    }
    return ans;
  }
};

func combinationSum3(k int, n int) (ans [][]int) {
  for mask := 0; mask < 1<<9; mask++ {
    if bits.OnesCount(uint(mask)) == k {
      t := []int{}
      s := 0
      for i := 0; i < 9; i++ {
        if mask>>i&1 == 1 {
          s += i + 1
          t = append(t, i+1)
        }
      }
      if s == n {
        ans = append(ans, t)
      }
    }
  }
  return
}

function combinationSum3(k: number, n: number): number[][] {
  const ans: number[][] = [];
  for (let mask = 0; mask < 1 << 9; ++mask) {
    if (bitCount(mask) === k) {
      const t: number[] = [];
      let s = 0;
      for (let i = 0; i < 9; ++i) {
        if (mask & (1 << i)) {
          t.push(i + 1);
          s += i + 1;
        }
      }
      if (s === n) {
        ans.push(t);
      }
    }
  }
  return ans;
}

function bitCount(i: number): number {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}

public class Solution {
  public IList<IList<int>> CombinationSum3(int k, int n) {
    List<IList<int>> ans = new List<IList<int>>();
    for (int mask = 0; mask < 1 << 9; ++mask) {
      if (bitCount(mask) == k) {
        List<int> t = new List<int>();
        int s = 0;
        for (int i = 0; i < 9; ++i) {
          if ((mask >> i & 1) == 1) {
            s += i + 1;
            t.Add(i + 1);
          }
        }
        if (s == n) {
          ans.Add(t);
        }
      }
    }
    return ans;
  }

  private int bitCount(int x) {
    int cnt = 0;
    while (x > 0) {
      x -= x & -x;
      ++cnt;
    }
    return cnt;
  }
}