39.combination-sum.md

组合总和

题目

思路

由题可知, 这是一个从数组中根据数字, 找出不同组合, 组合的和为target的值, 即可通过. 因此可采用回溯算法来解决该题.

1. 首先先对数组进行排序.
2. 设置一个指针集合, 默认初始为[0].
3. 然后根据这个指针集合, 取出对应的值进行求和判断.
4. 当和比目标值小时, 则新增当前指针, 继续求和判断.
5. 当和比目标值大或相等时, 则弹出最后的指针(数组经过排序, 无需比较右边的值), 同时将最右边的值右移动.
6. 如果相等还需另外将值传入最终结果集合.
7. 如果指针超出范围, 则弹出, 返回上一条件, 将指针右移.
8. 直到指针集合第一个指针超出范围. 完成全部查找. 返回结果.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  /** 排序 */
  candidates.sort((a, b) => a - b)

  const results = []
  const points = [0]
  const { length } = candidates

  while (points[0] < length) {
    let result = 0
    if (points[points.length - 1] === length) {
      pointsAdd(points)
    }
    for (let i = 0; i < points.length; i++) {
      result += candidates[points[i]]
    }
    if (result === target) {
      let tmp = []
      for (let i = 0; i < points.length; i++) {
        tmp.push(candidates[points[i]])
      }
      results.push(tmp)
      pointsAdd(points)
    }
    if (result > target) {
      /** 如果值比较大. 则返回上一个条件, 指针右移动, 继续查找 */
      pointsAdd(points)
    }
    if (result < target) {
      /** 如果值比较小. 则新增一个指针 */
      points.push(points[points.length - 1])
    }
  }
  return results
};
/**
 * @param {number[]} points 
 */
function pointsAdd (points) {
  if (points.length > 1) {
    points.pop()
  }
  const length = points.length
  points[length - 1] = points[length - 1] + 1
}

class Solution {
  /**
   * @param Integer[] $candidates
   * @param Integer $target
   * @return Integer[][]
   */
  function combinationSum($candidates, $target) {
    // 排序
    sort($candidates);

    $results = [];
    $points = [0];
    $length = count($candidates);
    while ($points[0] < $length) {
      $result = 0;
      if (end($points) >= $length) {
        $points = $this->pointsAdd($points);
      } else {
        for ($i = 0; $i < count($points); $i++) {
          $result += $candidates[$points[$i]];
        }
        if ($result  === $target) {
          $tmp = [];
          for ($i = 0; $i < count($points); $i++) {
            array_push($tmp, $candidates[$points[$i]]);
          }
          array_push($results, $tmp);
          $points = $this->pointsAdd($points);
        } else if ($result > $target) {
          $points = $this->pointsAdd($points);
        } else if ($result < $target) {
          array_push($points, end($points));
        }
      }
    }
    return $results;
  }
  /**
   * @param Integer[] $points
   */
  function pointsAdd ($points) {
    if (count($points) > 1) {
      array_pop($points);
    }
    $points[count($points) - 1] = end($points) + 1;
    return $points;
  }
}

class Solution {
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);

    List<List<Integer>> results = new ArrayList<>();
    List<Integer> points = new ArrayList<>();
    points.add(0);
    int length = candidates.length;

    while (points.get(0) < length) {
      int result = 0;

      if (points.get(points.size() - 1) == length) {
        pointsAdd(points);
      } else {
        for (int i = 0; i < points.size(); i++) {
          result += candidates[points.get(i)];
        }
  
        if (result == target) {
          List<Integer> tmp = new ArrayList<>();
          for (int i = 0; i < points.size(); i++) {
            tmp.add(candidates[points.get(i)]);
          }
          results.add(tmp);
          pointsAdd(points);
        } else if (result > target) {
          pointsAdd(points);
        } else if (result < target) {
          points.add(points.get(points.size() - 1));
        }
      }
    }

    return results;
  }

  public void pointsAdd (List<Integer> points) {
    if (points.size() > 1) {
      points.remove(points.size() - 1);
    }
    points.set(points.size() - 1, points.get(points.size() - 1) + 1);
  }
}