Nim Games: Is it possible to reduce following using Grundy Number? Following is the problem from a finished programming contest.


  Two players try to create a number, DesiredTotal, by adding numbers
  from 1 to N. The first to cross the number is the winner. The number to be
  added cannot be repeated. For example, if one player used 4 to increase the sum from
  20 to 24, the neither player can use 4 again in the game.


Now I understand how the above problem could be solved using dynamic programming by exploring all the possible paths and memoizing the solution, but the game being impartial still qualifies to be a Nim game.

Am I correct that, it is a Nim game? If yes, could somebody help me to reduce into a Nim game?

Below is the source but it requires signing in.

Theory: https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/

Source: https://leetcode.com/contest/leetcode-weekly-contest-10/problems/can-i-win/
Your game is an impartial game, and so it is covered by the Sprague–Grundy theorem, which say that it is equivalent to a "nimber". Note that the state of the game consists of the current value of the sum as well as the current set of allowed addends. You can compute the Grundy function, which gives the equivalence to Nim, using dynamic programming.